Encuentra los elementos faltantes y duplicados en una matriz en tiempo lineal y espacio constante

Te dan una matriz de enteros de N 64 bits. N puede ser muy grande. Sabes que cada entero 1..N aparece una vez en la matriz, excepto que hay un entero faltante y un entero duplicado.

Escribe un algoritmo de tiempo lineal para encontrar los números perdidos y duplicados. Además, su algoritmo debe ejecutarse en un pequeño espacio constante y dejar la matriz intacta.

Fuente: http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/

Si todos los números estuvieran presentes en la matriz, la sum sería N(N+1)/2 .

Determine la sum real sumndo todos los números en la matriz en O (n), sea esto Sum(Actual) .

Falta un número, que sea j y se duplique un número, que sea k . Eso significa que

Suma (real) = N (N + 1) / 2 + k – j

derivado de eso

k = Suma (real) -N (N + 1) / 2 + j

También podemos calcular la sum de cuadrados en la matriz, que sumría hasta n 3/3 + n 2/2 + n / 6 si todos los números estuvieran presentes.

Ahora podemos calcular la sum real de cuadrados en O (n), que esto sea Sum(Actual Squares) .

Suma (cuadrados reales) = n 3/3 + n 2/2 + n / 6 + k 2 – j 2

Ahora tenemos dos ecuaciones con las cuales podemos determinar j y k .

El truco de XOR funciona en dos pasadas con una matriz de solo lectura.

Esto evita el problema de posibles desbordamientos de enteros que tiene la sum y la sum de la solución de cuadrados.

Deje que los dos números sean y , uno de los cuales es el número que falta y el otro se repite.

XOR todos los elementos de la matriz, junto con 1,2,...,N

El resultado es w = x XOR y .

Ahora que x e y son distintos, w es distinto de cero.

Elija cualquier bit distinto de cero de w . x y y difieren en este bit. Digamos que la posición del bit es k .

Ahora considere una división de la matriz (y los números 1,2,...,N ) en dos conjuntos, en función de si el bit en la posición k es 0 o 1.

Ahora, si calculamos el XOR (por separado) de los elementos de los dos conjuntos, el resultado debe ser x e y .

Dado que el criterio para dividir es simplemente verificar si un bit está configurado como no, podemos calcular los dos XOR de los dos conjuntos haciendo otra pasada a través de la matriz y teniendo dos variables, cada una de las cuales contiene el XOR de los elementos vistos hasta ahora (y 1,2,...N ), para cada conjunto. Al final, cuando hayamos terminado, esas dos variables mantendrán x e y .

Relacionado:

  • Encontrar elementos faltantes en una matriz que se puede generalizar a m que aparece dos veces y falta m.

  • Encuentra tres números que aparecen una sola vez y faltan alrededor de tres.

Usando la idea básica de una pregunta de entrevista relacionada , podría hacer:

  • Suma todos los números (lo llamaremos S1 ) y sus cuadrados ( S2 )
  • Calcule la sum esperada de los números, sin modificaciones, es decir, E1 = n*(n+1)/2 y E2 = n*(n+1)*(2n+1)/6
  • Ahora sabes que E1 - S1 = d - m y E2 - S2 = d^2 - m^2 , donde d es el número duplicado y m el que falta.
  • Resuelve este sistema de ecuaciones y encontrarás que:

     m = 1/2 ((E2 - S2)/(E1 - S1) - (E1 - S1)) d = 1/2 ((E2 - S2)/(E1 - S1) + (E1 - S1)) // or even simpler: d = m + (E1 - S1) 

.

 $S1 = $S2 = 0; foreach ($nums as $num) { $S1 += $num; $S2 += $num * $num; } $D1 = $n * ($n + 1) / 2 - $S1; $D2 = $n * ($n + 1) * (2 * $n + 1) / 6 - $S2; $m = 1/2 * ($D2/$D1 - $D1); $d = 1/2 * ($D2/$D1 + $D1); 

Aquí hay una implementación de Java basada en la idea de @Aryabhatta:
Entrada: [3 1 2 5 3]
Salida: [3, 4]

 public ArrayList repeatedNumber(final List A) { ArrayList ret = new ArrayList<>(); int xor = 0, x = 0, y = 0; for(int i=0; i 

La solución propuesta por BrokenGlass cubre el caso de dos incógnitas (que corresponden a un número duplicado y un número que falta), utilizando dos fórmulas:

sum1

y

sum2

Las fórmulas producen el número armónico generalizado de órdenes n de -1 y -2, respectivamente. (Serie de potencia)

Esta solución se puede generalizar para 3 incógnitas incluyendo el valor del número armónico generalizado de orden n de -3.

sum3

Para resolver por m incógnitas (duplicados y números perdidos), use m números armónicos generalizados de órdenes n de -1 a -m.


Moron señala que este enfoque se discutió anteriormente en StackOverflow en la pregunta de entrevista fácil se hizo más difícil .

Tomando el leave the array untouched literalmente (es decir, la matriz puede modificarse temporalmente, siempre y cuando no cambie al final), se puede sugerir una solución orientada a la progtwigción.

Supongo que el tamaño de matriz N es mucho menor que 2 ^ 64, que es una cantidad de memoria totalmente poco realista. Entonces podemos suponer con seguridad que N < 2^P tal que P << 64 (significativamente más pequeño). En otras palabras, esto significa que todos los números en la matriz tienen algunos bits altos sin usar . Así que usemos el bit más alto como indicador si el índice de esa posición se ha visto en la matriz. El algoritmo es el siguiente:

  set HIGH = 2^63 // a number with only the highest bit set scan the array, for each number k do if array[k] < HIGH: array[k] = array[k] + HIGH // set the highest bit else: k is the duplicate for each i in 1..N do if array[i] < HIGH: i is missing else: array[i] = array[i] - HIGH // restore the original number 

Este es el tiempo lineal y muy poco cálculo

Código de Psuedo suponiendo que el conjunto está ordenado

 missing = nil duplicate = nil for i = 0, i < set.size - 1, i += 1 if set[i] == set[i + 1] duplicate = set[i] else if((set[i] + 1) != set[i+1]) missing = set[i] + 1 if missing != nil && duplicate != nil break return (missing, duplicate)