En tiempo menos que lineal, busque el duplicado en una matriz ordenada

Question

Hoy, un entrevistador me hizo esta pregunta. Mi respuesta inmediata fue que simplemente podíamos hacer una búsqueda lineal, comparando el elemento actual con el elemento anterior en la matriz. Luego me preguntó cómo se podía resolver el problema en un tiempo no lineal.

Supuestos

• la matriz es ordenados
• Sólo hay uno duplicar
• La matriz es solamente poblado con los números [0, n], donde n es la longitud de la formación.

Ejemplo de array: [0,1,2,3,4,5,6,7,8,8,9]

I trató de llegar a un divide y vencerás algoritmo para resolver esto, pero no estoy seguro de que fuera la respuesta correcta. ¿Alguien tiene alguna idea?

Answer 1

puede hacerse en O (log N) con una búsqueda binaria modificada:

Start en el medio de la matriz: Si array [idx] < idx el duplicado está a la izquierda, de lo contrario a la derecha. Enjuague y repita.

Answer 2

Intenté encontrar un algoritmo de dividir y vencer para resolver esto, pero no estoy seguro de que fuera la respuesta correcta.

Claro, usted podría hacer una búsqueda binaria.

Si el arr[i/2] >= i/2 el duplicado se encuentra en la mitad superior de la matriz, de lo contrario, se encuentra en la mitad inferior.

while (lower != upper) 
    mid = (lower + upper)/2 
    if (arr[mid] >= mid) 
     lower = mid 
    else 
     upper = mid-1 

Desde la matriz entre lower y upper se redujo a la mitad en cada iteración, el algoritmo se ejecuta en O (log n).

ideone.com demo in Java

Answer 3

Si no hay ningún número no se encuentra en la matriz, como en el ejemplo, es factible en O (log n) con una búsqueda binaria. Si a[i] < i, el duplicado es anterior a i, de lo contrario es posterior a i.

Si hay un número ausente y uno por duplicado, aún sabemos que si a[i] < i el duplicado debe ser antes de i y si a[i] > i, el número ausente debe ser antes i y el duplicado después. Sin embargo, si a[i] == i, no sabemos si el número y el duplicado faltantes están antes de i o ambos después de i. No veo una manera para un algoritmo sublineal en ese caso.

Answer 4

La matriz de ejemplo es un poco diferente de su pregunta. Como n es la longitud de la matriz y hay una sola duplicada en la matriz, el valor de cada elemento en la matriz debe estar en [0, n-1].

Si esto es cierto, entonces esta pregunta es la misma con How to find a duplicate element in an array of shuffled consecutive integers?

El siguiente código debe encontrar el duplicado en tiempo O (n) y O (1) espacio.

public static int findOnlyDuplicateFromArray(int[] a, boolean startWithZero){ 
    int xor = 0; 
    int offset = 1; 
    for(int i=0; i < a.length; i++){ 
     if(startWithZero) 
      xor = xor^(a[i] + offset)^i; 
     else 
      xor = xor^a[i]^i; 
     } 
     if(startWithZero) 
      xor = xor - offset; 
    return xor; 
} 

Answer 5

¿Qué tal eso? (Estilo recursión)

public static int DuplicateBinaryFind(int[] arr, int left, int right) 
{ 
    int dup =0; 

    if(left==right) 
    { 
     dup = left; 
    } 
    else 
    { 
     int middle = (left+right)\2; 
     if(arr[middle]<middle) 
     { 
      dup = DuplicateBinaryFind(arr,left, middle-1); 

     } 
     else 
     { 
      dup = DuplicateBinaryFind(arr, middle+1, right); 
     } 
    } 

    return dup; 

} 

Answer 6

Diferencia entre suma de elementos de la matriz dados y suma de 0 a n-1 números naturales le da el elemento duplicado. Suma de 0 a n-1 elementos es (N * N-1)/2 matriz de ejemplo es [0,1,2,3,4,5,6,7,8,8,9] suma de 0 a 9 números naturales es: 45 suma de elementos de matriz dados: 53 53-45 = 8 Cuál es el elemento duplicado