¿Cuál es la forma óptima de calcular qué número entero en una lista falta?

Question

Hace poco estuve en una entrevista donde me hicieron preguntas técnicas. Una era cómo calcularía qué número de una lista de longitud n-1 faltaba. La lista contenía todos los números de 1 a n, excepto en donde 1 < = i < = n. Los números no estaban en orden. Mi solución fue sumarlos todos, luego restarlos del cálculo de los números de 1 a n, agregando 1 a ny multiplicando por n/2 o (n-1)/2 según corresponda. Pero tuve la sensación de que había una mejor manera de hacerlo. ¿Cuál es la solución óptima?

Answer 1

Su respuesta es lo suficientemente buena, en mi opinión.

Pero algunas personas, tal vez su entrevistador es uno de ellos, están preocupados por el desbordamiento y tal. En ese caso, use XOR en lugar de agregar.

Para obtener el XOR de los números enteros de 0 a n, simplemente combine XOR junto con los índices de la matriz mientras realiza el ciclo. Dado el XOR de los enteros de 0 a n, y el XOR de los elementos de la matriz, simplemente XOR los dos juntos para obtener el elemento faltante.

P.S. La suma de los enteros de 1 a n es siempre (n + 1) * n/2

Answer 2

Mientras recorre la matriz para calcular la suma, puede verificar si un número se repite.

Answer 3

Su método es absolutamente correcto. Es óptimo en términos de espacio y tiempo. El desbordamiento puede ser el único problema.

Otro posible método podría ser el uso de un hashSet. Cree un hashSet inicial que tenga los valores 1-> N. Ahora, para cada número que encuentre en la lista, elimine ese valor de hashSet. Al final, el valor que permanece en hashSet es el valor que falta.

Este método es O (N) en complejidad de tiempo y espacio. Su método (salvo desbordamiento) fue O (N) en el tiempo y O (1) complejidad. El factor agregado 'n' para el espacio es el costo para eliminar el desbordamiento.

Answer 4

Su solución es más o menos óptimo con un cambio, como señala @Nemo a cabo la suma de los números enteros de 1 a n es siempre (n+1) * n/2

También vale la pena señalar que el enfoque es multi-hilo capaz (y podría adecuado para valores muy grandes de N), divida la matriz en partes, luego obtenga la suma de cada parte de la matriz en una secuencia, luego agregue esas sumas de parte. Depende de cómo se compara la sobrecarga de subprocesos con la adición de números en una matriz.

Si le preocupan los desbordamientos, y sus valores son siempre int32 (ya que la mayoría de los valores .Length incluyen matrices) simplemente almacene la suma como un int64, la suma de todos los valores enteros positivos (((long)int.MaxValue) +1L) * (int.MaxValue/2) = 2305843007066210304 que aún puede caber dentro de un int64 con un .MaxValue = 9223372036854775807.

La otra respuesta mencionada por otros es para XOR cada elemento y mantener un XOR en ejecución, pero luego tiene que encontrar una fórmula para obtener el XOR total esperado en O(1) vez.

Lo más probable es que el entrevistador está buscando para ver si se da cuenta que hay una solución O(N) con O(1) memoria (que su respuesta es), en lugar de la clasificación de la matriz y siendo mucho más lento para valores muy grandes de N.

Para mejorar aún más su solución en el código, sería utilizar un puntero para acceder a la matriz en lugar del valor del índice (que si su código es C# será una mejora razonable).