Encuentra duplicados en tiempo O(n) y espacio extra O(1) | Serie 1

Dada una array de n elementos que contiene elementos de 0 a n-1, cualquiera de estos números aparece cualquier número de veces. Encuentre estos números repetidos en O (n) y use solo espacio de memoria constante.

Ejemplo: 

Input : n = 7 and array[] = {1, 2, 3, 6, 3, 6, 1}
Output: 1, 3, 6

Explanation: The numbers 1 , 3 and 6 appears more
than once in the array.

Input : n = 5 and array[] = {1, 2, 3, 4 ,3}
Output: 3

Explanation: The number 3 appears more than once
in the array.

Este problema es una versión extendida del siguiente problema.  
Encuentre los dos elementos repetidos en una array dada 
. El Método 1 y el Método 2 del enlace anterior no son aplicables ya que la pregunta dice O (n) complejidad de tiempo y O (1) espacio constante. Además, el Método 3 y el Método 4 no se pueden aplicar aquí porque puede haber más de 2 elementos repetidos en este problema. El método 5 se puede extender para que funcione en este problema. A continuación se muestra la solución que es similar al Método 5.

Enfoque eficiente:

• Enfoque: Los elementos en la array son de 0 a n-1 y todos ellos son positivos. Entonces, para encontrar los elementos duplicados, se requiere un HashMap, pero la cuestión es resolver el problema en el espacio constante. Hay una trampa, la array tiene una longitud de n y los elementos son de 0 a n-1 (n elementos). La array se puede utilizar como HashMap. 
  Problema en el siguiente enfoque. Este enfoque solo funciona para arrays que tienen como máximo 2 elementos duplicados, es decir, no funcionará si la array contiene más de 2 duplicados de un elemento. Por ejemplo: {1, 6, 3, 1, 3, 6, 6} dará como resultado: 1 3 6 6.
• Nota: El programa anterior no maneja 0 casos (si 0 está presente en la array). El programa se puede modificar fácilmente para manejar eso también. No se maneja para mantener el código simple. (El programa se puede modificar para manejar 0 casos agregando más Uno (+1) a todos los valores. También restando Uno de la respuesta y escribiendo { arr [abs (arr [i]) – 1] } en el código)

En otro enfoque a continuación, la solución discutida imprime elementos repetidos solo una vez.

• Enfoque: La idea básica es usar un HashMap para resolver el problema. Pero hay un problema, los números en la array van del 0 al n-1, y la array de entrada tiene una longitud n. Entonces, la array de entrada se puede usar como HashMap. Mientras atraviesa la array, si se encuentra un elemento ‘a’, aumente el valor de un% n’ésimo elemento en n. La frecuencia se puede recuperar dividiendo el elemento a % n por n.
• Algoritmo: 
  1. Recorre la array dada de principio a fin.
  2. Para cada elemento de la array, incremente el elemento arr[i]%n’th en n.
  3. Ahora recorra la array nuevamente e imprima todos esos índices i para los cuales arr[i]/n es mayor que 1. Lo que garantiza que el número n se ha agregado a ese índice
  4. Este enfoque funciona porque todos los elementos están en el rango de 0 a n-1 y arr[i] sería mayor que n solo si ha aparecido un valor «i» más de una vez.

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

// C++ code to find
// duplicates in O(n) time
#include <bits/stdc++.h>
using namespace std;
  
int main()
{
    int numRay[] = { 0, 4, 3, 2, 7, 8, 2, 3, 1 };
    int arr_size = sizeof(numRay) / sizeof(numRay[0]);
    // count the frequency
    for (int i = 0; i < arr_size; i++) {
        numRay[numRay[i] % arr_size]
            = numRay[numRay[i] % arr_size] + arr_size;
    }
    cout << "The repeating elements are : " << endl;
    for (int i = 0; i < arr_size; i++) {
        if (numRay[i] >= arr_size * 2) {
            cout << i << " " << endl;
        }
    }
    return 0;
}
  
// This code is contributed by aditya kumar (adityakumar129)

// C++ code to find
// duplicates in O(n) time
  
#include <stdio.h>
  
int main()
{
  
    int numRay[] = { 0, 4, 3, 2, 7, 8, 2, 3, 1 };
    int arr_size = sizeof(numRay) / sizeof(numRay[0]);
    
    
    // count the frequency
    for (int i = 0; i < arr_size; i++) {
        numRay[numRay[i] % arr_size]
            = numRay[numRay[i] % arr_size] + arr_size;
    }
    printf("The repeating elements are : \n");
    for (int i = 0; i < arr_size; i++) {
        if (numRay[i] >= arr_size * 2) {
            printf("%d  \n", i );
        }
    }
    return 0;
}
// This code is contributed by aditya kumar (adityakumar129)

// JAVA code to find
// duplicates in O(n) time
  
class Leet442 {
  
    public static void main(String args[])
    {
        int numRay[] = { 0, 4, 3, 2, 7, 8, 2, 3, 1 };
  
        for (int i = 0; i < numRay.length; i++) {
            numRay[numRay[i] % numRay.length]
                = numRay[numRay[i] % numRay.length]
                  + numRay.length;
        }
        System.out.println("The repeating elements are : ");
        for (int i = 0; i < numRay.length; i++) {
            if (numRay[i] >= numRay.length * 2) {
                System.out.println(i + " ");
            }
        }
    }
}

# Python3 code to find duplicates in O(n) time
numRay = [0, 4, 3, 2, 7, 8, 2, 3, 1]
arr_size = len(numRay)
for i in range(arr_size):
  
    x = numRay[i] % arr_size
    numRay[x] = numRay[x] + arr_size
  
print("The repeating elements are : ")
for i in range(arr_size):
    if (numRay[i] >= arr_size*2):
        print(i, " ")
  
# This code is contributed by 29AjayKumar

// C# code to find
// duplicates in O(n) time
using System;
class Leet442 
{
    public static void Main(String []args)
    {
        int []numRay = { 0, 4, 3, 2, 7, 8, 2, 3, 1 };
  
        for (int i = 0; i < numRay.Length; i++) 
        {
            numRay[numRay[i] % numRay.Length]
                = numRay[numRay[i] % numRay.Length]
                + numRay.Length;
        }
        Console.WriteLine("The repeating elements are : ");
        for (int i = 0; i < numRay.Length; i++) 
        {
            if (numRay[i] >= numRay.Length * 2) 
            {
                Console.WriteLine(i + " ");
            }
        }
    }
}
  
// This code is contributed by shivanisinghss2110

<script>
    // Javascript code to find
    // duplicates in O(n) time
    let numRay = [ 0, 4, 3, 2, 7, 8, 2, 3, 1 ];
    let arr_size = numRay.length;
     
     
    // count the frequency
    for (let i = 0; i < arr_size; i++) {
        numRay[numRay[i] % arr_size]
            = numRay[numRay[i] % arr_size] + arr_size;
    }
    document.write("The repeating elements are : " + "</br>");
    for (let i = 0; i < arr_size; i++) {
        if (numRay[i] >= arr_size * 2) {
            document.write(i + " " + "</br>");
        }
    }
  
// This code is contributed by mukesh07.
</script>

The repeating elements are : 
2 
3 

Análisis de Complejidad: 

• Complejidad de tiempo: O (n), solo se necesitan dos recorridos. Entonces la complejidad del tiempo es O(n).
• Espacio Auxiliar: O(1), No se necesita espacio adicional, por lo que la complejidad del espacio es constante.

Otro enfoque eficiente: modificar la array haciendo que los elementos visitados sean -ve (visitados una vez) o mayores que n (visitados dos veces o más)

• Enfoque:
  Incremente los elementos de la array en 1 (arr[i]+1) para manejar la ocurrencia de 0. Recorra la array y para cada elemento que haya sido visitado por primera vez, haga que el elemento en el índice sea igual al valor del elemento actual como negativo. Si el elemento ya ha sido visitado anteriormente, agréguelo (arr[i]-1) al vector de resultados y haga que el elemento en el índice sea igual al valor del elemento actual más de n (multiplicándolo con (n+1)) para evitar agregándolo al vector de resultados, en caso de que ocurra nuevamente. 
• Algoritmo :
  • Recorra la array e incremente cada elemento en 1. Esto se hace para eliminar la ocurrencia de 0 de la array. Más tarde, mientras agregamos los elementos duplicados en el vector de resultados, disminuimos los elementos en 1 para obtener el valor real.
  • Declarar vector de resultado.
  • Declare una variable de conteo para contar la aparición del (n-1) elemento en la array. 
    Por ejemplo: array = [0,2,4,3,4], n=5, entonces necesitamos la variable de conteo para contar la ocurrencia de 4. 
    En el algoritmo, necesitamos acceder a elementos presentes en el índice igual a otros valores de elementos, lo que significa que tenemos que acceder a valores como array[array[i]]. Por ejemplo: si i=0, accedemos a array[array[i]] = array[array[0]] = array[1] = 2. De manera similar, es posible que necesitemos acceder al elemento en el índice igual al valor más grande posible en la array, es decir, n-1 (array[array[n-1]]). Sin embargo, incrementamos cada elemento en 1 y, por lo tanto, el elemento más grande posible en la array se convirtió en n. En la indexación basada en 0, la array [n] devuelve un valor de basura y, por lo tanto, nuestro algoritmo no puede calcular la aparición del elemento más grande posible en la array. Por lo tanto, necesitamos la variable de conteo para contar su ocurrencia por separado y luego agregarla al vector de resultados si se encuentra duplicada.
  • Ejecute un ciclo for de 0 a n y en cada iteración del ciclo:
    • Calcular valor de índice: 
      dado que necesitamos acceder a los elementos presentes en el índice igual a otros valores de elementos, el índice es el valor absoluto de arr[i]. Si abs(arr[i]) es mayor que n, entonces el índice es igual a abs(arr[i])/(n+1) sino abs(arr[i]). 
      Si un elemento ‘x’ aparece dos veces en el arreglo, negamos el elemento presente en x, es decir, arreglo[x] = -arreglo[x], pero si aparece más de dos veces, entonces, para evitar que sea empujado a vector de resultado nuevamente, hacemos que el elemento en x sea igual a un número mayor que n (un número que nunca ocurriría en la array). Para ello, lo multiplicamos por (n+1), es decir, array[x] = array[x]*(n+1). No podemos multiplicar con n como si array[x] = 1, luego array[x]*n = n, que es el elemento más grande posible y puede aparecer en la array. 
      Por lo tanto, durante el recorrido, si nos encontramos con una array[x] que es mayor que n, debemos calcular la array[x]/(n+1) para obtener el valor original de índice.
       
    • Verifique si el valor del índice obtenido es igual a n, si es así, incremente la variable de conteo y pase a la siguiente iteración, ya que calcularemos la ocurrencia de n por separado.
       
    • Obtenga el valor del elemento en el índice calculado en una variable y ejecute las siguientes condiciones else-if:
      • Si este valor es menor que 0 (-ve), significa que el elemento igual a su índice ha aparecido dos veces, por lo tanto, inserte el valor de índice-1 (ya que los valores de los elementos se incrementaron anteriormente) en el vector de resultados. En el futuro, como este valor de índice ya se ha enviado al vector de resultados, no queremos un duplicado en el vector de resultados si vuelve a ocurrir y, por lo tanto, hacer que el valor del elemento presente en este índice sea mayor que n multiplicándolo por ( n+1).
      • Si este valor es mayor que n, significa que el elemento igual al valor del índice ya se ha enviado al vector de resultados y no es necesario hacer nada. Así que continúa con la siguiente iteración.
      • Si este valor está entre 0 y n, significa que el elemento igual al valor del índice ha aparecido por primera vez y, por lo tanto, lo convierte en negativo.
         
  • Después de salir del bucle for, si el valor de la variable de conteo es mayor que 1, significa que el elemento más grande posible (n) tiene duplicados en la array y, por lo tanto, empuja (n-1) al vector de resultados.
  • Verifique si el tamaño del vector de resultado es 0, si es así, presione -1 ya que no hay duplicados. De lo contrario, ordene el vector de resultado
  • Devuelve el vector de resultado.

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

#include <bits/stdc++.h>
using namespace std;
  
vector<int> duplicates(int arr[], int n)
{
  
    // Increment array elements by 1
    for (int i = 0; i < n; i++) {
        arr[i] += 1;
    }
  
    // result vector
    vector<int> res;
  
    // count variable for count of
    // largest element
    int count = 0;
  
    for (int i = 0; i < n; i++) {
  
        // Calculate index value
        int index = abs(arr[i]) > n ? abs(arr[i]) / (n + 1)
                                    : abs(arr[i]);
  
        // Check if index equals largest element value
        if (index == n) {
            count++;
            continue;
        }
  
        // Get element value at index
        int val = arr[index];
  
        // Check if element value is negative, positive
        // or greater than n
        if (val < 0) {
            res.push_back(index - 1);
            arr[index] = abs(arr[index]) * (n + 1);
        }
        else if (val > n)
            continue;
        else
            arr[index] = -arr[index];
    }
  
    // If largest element occurs more than once
    if (count > 1)
        res.push_back(n - 1);
  
    if (res.size() == 0)
        res.push_back(-1);
    else
        sort(res.begin(), res.end());
  
    return res;
}
  
// Driver Code
int main()
{
    int numRay[] = { 0, 4, 3, 2, 7, 8, 2, 3, 1 };
    int n = sizeof(numRay) / sizeof(numRay[0]);
  
    vector<int> ans = duplicates(numRay, n);
    for (int i : ans)
        cout << i << ' ' << endl;
    return 0;
}

2 
3 

Análisis de Complejidad:

• Complejidad de tiempo: O (n), solo se necesitan dos recorridos. Entonces la complejidad del tiempo es O(n).
• Espacio Auxiliar: O(1).