c++ - repetir - encontrar el número duplicado en una matriz

numeros repetidos en una matriz c++

Question

Estoy depurando debajo del problema y publicando la solución que estoy depurando y trabajando, la solución o similar se publica en un par de foros, pero creo que la solución tiene un error cuando num [0] = 0 o en general num [x] = x? ¿Estoy en lo correcto? Por favor, siéntete libre de corregirme si me equivoco.

Dado un conjunto nums que contiene n + 1 enteros donde cada entero está entre 1 yn (inclusive), demuestre que debe existir al menos un número duplicado. Suponga que solo hay un número duplicado, encuentre el duplicado.

Nota: No debe modificar la matriz (suponga que la matriz es de solo lectura). Debe usar solo constante, O (1) espacio extra. La complejidad de su tiempo de ejecución debe ser menor que O (n2). Solo hay un número duplicado en la matriz, pero podría repetirse más de una vez.

int findDuplicate3(vector<int>& nums)
{
    if (nums.size() > 1)
    {
        int slow = nums[0];
        int fast = nums[nums[0]];
        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        fast = 0;
        while (fast != slow)
        {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
    return -1;
}

Answer 1

Como no puede usar ningún espacio adicional, se descartaría usar otra tabla hash.

Ahora, llegando al enfoque de hash en la matriz existente, se puede lograr si se nos permite modificar la matriz en su lugar.

Algo:

1) Comience con el primer elemento.

2) Haga clic en el primer elemento y aplique una transformación al valor de hash. Digamos que esta transformación está haciendo el valor -ve.

3) Continúe con el siguiente elemento. Mantenga presionado el elemento y antes de aplicar la transformación, verifique si ya se ha aplicado una transformación.

4) Si es así, entonces el elemento es un duplicado.

Código:

 for(i = 0; i < size; i++)
  {
    if(arr[abs(arr[i])] > 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      cout<< abs(arr[i]) <<endl;
  }  

Esta transformación es necesaria ya que si vamos a utilizar el método de hashing, entonces, tiene que haber una colisión para hash la misma clave.

No puedo pensar en una forma en que se pueda usar hashing sin espacio adicional y sin modificar la matriz.

Answer 2

La suma de enteros de 1 a N = (N * (N + 1)) / 2 . Puede usar esto para encontrar el duplicado: sumar los enteros en la matriz, luego restar la fórmula anterior de la suma. Ese es el duplicado.

Actualización : la solución anterior se basa en la suposición (posiblemente no válida) de que la matriz de entrada consiste en los valores de 1 a N más un único duplicado.

Answer 3

A continuación está mi código que usa el algoritmo de búsqueda de ciclos de Floyd :

#include <iostream>
#include <vector>
using namespace std;

int findDup(vector<int>&arr){
    int len = arr.size();
    if(len>1){
        int slow = arr[0];
        int fast = arr[arr[0]];
        while(slow!=fast){
            slow = arr[slow];
            fast = arr[arr[fast]];
        }
        fast = 0;
        while(slow!=fast){
            slow = arr[slow];
            fast = arr[fast];
        }
        return slow;
    }
    return -1;
}

int main() {
    vector<int>v = {1,2,2,3,4};
    cout<<findDup(v)<<endl;
    return 0;
}

Comentario Esto funciona porque los ceros no están permitidos, por lo que el primer elemento de la matriz no es parte de un ciclo, por lo que el primer elemento del primer ciclo que encontramos se refiere tanto al exterior como al interior del ciclo. Si se permitieran ceros, esto fallaría si arr [0] estuviera en un ciclo. Por ejemplo, [0,1,1].

Answer 4

1. Comience con dos punteros al primer elemento: rápido y lento .
2. Defina un ''movimiento'' como incremento rápido en 2 pasos (posiciones) y disminuya en 1.
3. Después de cada movimiento , verifique si el punto lento y rápido está en el mismo nodo.
4. Si hay un bucle, en algún momento lo harán. Esto se debe a que, después de que ambos están en el bucle, el rápido se mueve dos veces más rápido que el lento y eventualmente se ''ejecutará'' en él.
5. Dicen que se encuentran después de k movimientos . Este NO es NECESARIAMENTE el elemento repetido, ya que podría no ser el primer elemento del ciclo alcanzado desde fuera del ciclo.
   Llamar a este elemento X
6. Observe que el rápido ha avanzado 2 veces, y el lento ha aumentado k veces.
7. Mueve rápidamente a cero.
8. Avance repetidamente rápido y lento por UN PASO CADA UNO, comparando después de cada paso.
9. Tenga en cuenta que después de otros k pasos, slow habrá movido un total de 2k pasos y acelerará un total de k pasos desde el inicio, por lo que ambos nuevamente apuntarán a X.
10. Observe que si el paso anterior está en el bucle para ambos, ambos estaban apuntando a X-1 . Si el paso anterior solo estaba en el bucle lento , estaban apuntando a diferentes elementos.
11. Lo mismo para X-2, X-3, ...
12. Entonces, al avanzar, la primera vez que apuntan al mismo elemento es el primer elemento del ciclo alcanzado desde fuera del ciclo, que es el elemento repetido que está buscando.