Recuento de un solo elemento repetido en una array ordenada de elementos consecutivos

Dada una array ordenada de elementos consecutivos. La array tiene un solo elemento repetido muchas veces. La tarea es encontrar la longitud de la secuencia de los elementos repetidos.

Complejidad de tiempo esperada: Menos de 0(n)

Ejemplos: 

Entrada: arr[] = {1, 2, 3, 4, 4, 4, 5, 6}
Salida: 4 3
El elemento repetido es 4 y aparece 3 veces.

Entrada: arr[] = {4, 4, 4, 4, 4}
Salida: 4 5 

Entrada: arr[] = {6, 7, 8, 9, 10, 10, 11}
Salida: 10 2

Entrada: arr[] = {6, 7, 8, 9, 10, 10, 10}
Salida: 10 3 

Enfoque: Necesitamos encontrar dos cosas:  

• Para encontrar el número de veces que se repite el elemento: 
  • Supongamos que no hay un elemento repetido para una array dada, entonces el elemento menor estará en arr[0] y el elemento más alto estará en arr[n-1].
  • Ahora, cada vez que se repite un elemento, el elemento más alto disminuirá en 1 cada vez.
  • Basado en esta idea, dado que la array está ordenada y la diferencia máxima de dos elementos adyacentes es 1, entonces: 

recuento de elementos únicos = arr[n-1] – arr[0]

Por lo tanto,
longitud del elemento repetido = n – recuento de elementos únicos 
                                                               = n – (array[n-1] – array[0])

• Para encontrar el valor del elemento repetido: 
  • Para encontrar el valor repetido, podemos usar la búsqueda binaria . 

A continuación se muestra la implementación del enfoque anterior:

// C++ program to find the only repeated element
// and number of times it appears
#include <bits/stdc++.h>
using namespace std;
 
// Assumptions : vector a is sorted, max-difference
// of two adjacent elements is 1
pair<int, int> sequence(const vector<int>& a)
{
    if (a.size() == 0)
        return {0, 0};
 
    int s = 0;
    int e = a.size() - 1;
    while (s < e)
    {
        int m = (s + e) / 2;
 
        // if a[m] = m + a[0], there is no
        // repeating character in [s..m]
        if (a[m] >= m + a[0])
            s = m + 1;
 
       // if a[m] < m + a[0], there is a
       // repeating character in [s..m]
        else
            e = m;
    }
    return {a[s], a.size() - (a[a.size() - 1] - a[0])};
}
 
// Driver code
int main()
{
    pair<int, int>p = sequence({ 1, 2, 3, 4, 4, 4, 5, 6 });
    cout << "Repeated element is " << p.first
         << ", it appears " << p.second << " times";
    return 0;
}

// Java program to find the only repeated element
// and number of times it appears
 
import java.awt.Point;
import java.util.Arrays;
import java.util.Vector;
 
class Test
{
    // Assumptions : vector a is sorted, max-difference
    // of two adjacent elements is 1
    static Point sequence(Vector<Integer> a)
    {
        if (a.size() == 0)
            return new Point(0, 0);
      
        int s = 0;
        int e = a.size() - 1;
        while (s < e)
        {
            int m = (s + e) / 2;
      
            // if a[m] = m + a[0], there is no
            // repeating character in [s..m]
            if (a.get(m) >= m + a.get(0))
                s = m + 1;
      
           // if a[m] < m + a[0], there is a
           // repeating character in [s..m]
            else
                e = m;
        }
        return new Point(a.get(s), a.size() - (a.get(a.size() - 1) - a.get(0)));
    }
     
    // Driver method
    public static void main(String args[])
    {
        Integer array[] = new Integer[]{1, 2, 3, 4, 4, 4, 5, 6};
        Point p = sequence(new Vector<>(Arrays.asList(array)));
        System.out.println("Repeated element is " + p.x +
                           ", it appears " + p.y + " times");
    }
}

# Python3 program to find the
# only repeated element and
# number of times it appears
 
# Assumptions : vector a is sorted,
# max-difference of two adjacent
# elements is 1
def sequence(a):
    if (len(a) == 0):
        return [0, 0]
 
    s = 0
    e = len(a) - 1
    while (s < e):
        m = (s + e) // 2
 
        # if a[m] = m + a[0], there is no
        # repeating character in [s..m]
        if (a[m] >= m + a[0]):
            s = m + 1
 
        # if a[m] < m + a[0], there is a
        # repeating character in [s..m]
        else:
            e = m
    return [a[s], len(a) - (
                a[len(a) - 1] - a[0])]
 
# Driver code
p = sequence([1, 2, 3, 4, 4, 4, 5, 6])
print("Repeated element is", p[0],
             ", it appears", p[1], "times")
 
# This code is contributed by Mohit Kumar

// C# program to find the only repeated element
// and number of times it appears
using System;
using System.Collections.Generic;
 
public class Point
{
    public int first, second;
 
        public Point(int first, int second)
        {
            this.first = first;
            this.second = second;
        }
     
     
}
public class Test
{
    // Assumptions : vector a is sorted, max-difference
    // of two adjacent elements is 1
    static Point sequence(List<int> a)
    {
        if (a.Count == 0)
            return new Point(0, 0);
     
        int s = 0;
        int e = a.Count - 1;
        while (s < e)
        {
            int m = (s + e) / 2;
     
            // if a[m] = m + a[0], there is no
            // repeating character in [s..m]
            if (a[m] >= m + a[0])
                s = m + 1;
     
        // if a[m] < m + a[0], there is a
        // repeating character in [s..m]
            else
                e = m;
        }
        return new Point(a[s], a.Count - (a[a.Count - 1] - a[0]));
    }
     
    // Driver code
    public static void Main(String []args)
    {
        int []array = new int[]{1, 2, 3, 4, 4, 4, 5, 6};
        Point p = sequence(new List<int>(array));
        Console.WriteLine("Repeated element is " + p.first +
                        ", it appears " + p.second + " times");
    }
}
 
// This code has been contributed by 29AjayKumar

<script>
 
// Javascript program to find the only repeated element
// and number of times it appears
     
// Assumptions : vector a is sorted, max-difference
    // of two adjacent elements is 1   
function sequence(a)
{
    if (a.length == 0)
        return [0, 0]
   
    let s = 0
    let e = a.length - 1
    while (s < e)
    {
        let m = Math.floor((s + e) / 2);
   
        // if a[m] = m + a[0], there is no
        // repeating character in [s..m]
        if (a[m] >= m + a[0])
            s = m + 1
   
        // if a[m] < m + a[0], there is a
        // repeating character in [s..m]
        else
            e = m
    }
    return [a[s], a.length - (
                a[a.length - 1] - a[0])]
}
 
// Driver method
let p = sequence([1, 2, 3, 4, 4, 4, 5, 6])
document.write("Repeated element is "+ p[0]+
             ", it appears "+ p[1]+ " times")
     
 
// This code is contributed by patel2127
</script>

Repeated element is 4, it appears 3 times

Complejidad temporal: O(log n)
Espacio auxiliar: O(1)

Este artículo es una contribución de Rakesh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.