Encuentra un "agujero" en una lista de números

14

¿Cuál es la forma más rápida de encontrar el primer entero (más pequeño) que no existe en una lista dada de enteros sin clasificar (y que es mayor que el valor más pequeño de la lista)?

Mi enfoque primitivo es ordenarlos y recorrer la lista, ¿hay una mejor manera?

Fabian Zeindl
fuente
66
@Jodrell Creo que ordenar una progresión infinita sería difícil ;-)
maple_shaft
3
@maple_shaft estuvo de acuerdo, podría tomar un tiempo.
Jodrell
44
¿Cómo se define primero para una lista sin clasificar?
Jodrell
1
Me acabo de dar cuenta de que esto probablemente pertenece a StackOverflow, ya que no es realmente un problema conceptual.
JasonTrue
2
@JasonTrue De las preguntas frecuentes, If you have a question about… •algorithm and data structure conceptsestá en el tema en mi humilde opinión.
maple_shaft

Respuestas:

29

Suponiendo que quiere decir "entero" cuando dice "número", puede usar un vector de bits de tamaño 2 ^ n, donde n es el número de elementos (digamos que su rango incluye enteros entre 1 y 256, entonces puede usar un 256- bit, o 32 byte, bitvector). Cuando encuentre un número entero en la posición n de su rango, establezca el enésimo bit.

Cuando haya terminado de enumerar la colección de enteros, iterará sobre los bits en su vector de bits, buscando la posición de cualquier conjunto de bits 0. Ahora coinciden con la posición n de sus enteros faltantes.

Esto es O (2 * N), por lo tanto, O (N) y probablemente sea más eficiente en memoria que ordenar toda la lista.

JasonTrue
fuente
66
Bueno, como comparación directa, si tuviera todos los enteros positivos de 32 bits sin signo pero 1, podría resolver el problema de los enteros faltantes en aproximadamente medio gigabyte de memoria. Si ordenó en su lugar, tendría que usar más de 8 gigabytes de memoria. Y la clasificación, excepto en casos especiales como este (su lista se ordena una vez que tiene un vector de bits) es casi siempre n log n o peor, así que excepto en los casos en que la constante supera la complejidad en el costo, el enfoque lineal gana.
JasonTrue
1
¿Qué pasa si no conoce el rango a priori?
Blrfl
2
Si tiene un tipo de datos entero, Blrfl, ciertamente conoce las extensiones máximas del rango, incluso si no tiene suficiente información para limitarse aún más. Si sabe que es una lista pequeña, pero no sabe el tamaño exacto, la clasificación podría ser una solución más simple.
JasonTrue
1
O haga otro ciclo primero a través de la lista para encontrar el elemento más pequeño y el más grande. Luego puede asignar una matriz de tamaño exacto con el valor más pequeño como el desplazamiento básico. Todavía en).
Seguro el
1
@JPatrick: No es tarea, negocios, me gradué de CS hace años :).
Fabian Zeindl
4

Si primero ordena la lista completa, entonces garantiza el peor tiempo de ejecución. Además, su elección del algoritmo de clasificación es crítica.

Así es como abordaría este problema:

  1. Use una ordenación de montón , centrándose en los elementos más pequeños de la lista.
  2. Después de cada intercambio, vea si tiene un espacio.
  3. Si encuentra una brecha, entonces return: Ha encontrado su respuesta.
  4. Si no encuentra una brecha, continúe intercambiando.

Aquí hay una visualización de una especie de montón .

Jim G.
fuente
Una pregunta, ¿cómo identifica los elementos "más pequeños" de la lista?
Jodrell
4

Solo para ser esotérico e "inteligente", en el caso especial de que la matriz tenga solo un "agujero", puede probar una solución basada en XOR:

  • Determine el rango de su matriz; esto se hace estableciendo una variable "max" y "min" en el primer elemento de la matriz, y para cada elemento después de eso, si ese elemento es menor que el mínimo o mayor que el máximo, establezca el mínimo o máximo en nuevo valor.
  • Si el rango es uno menor que la cardinalidad del conjunto, solo hay un "agujero" para que pueda usar XOR.
  • Inicializa una variable entera X a cero.
  • Para cada número entero de min a max inclusive, XOR ese valor con X y almacena el resultado en X.
  • Ahora XOR cada número entero en la matriz con X, almacenando cada resultado sucesivo en X como antes.
  • Cuando haya terminado, X será el valor de su "agujero".

Esto se ejecutará en aproximadamente 2N tiempo similar a la solución de vector de bits, pero requiere menos espacio de memoria para cualquier N> sizeof (int). Sin embargo, si la matriz tiene múltiples "agujeros", X será la "suma" XOR de todos los agujeros, lo que será difícil o imposible de separar en los valores reales de los agujeros. En ese caso, recurre a algún otro método, como los enfoques de "pivote" o "vector de bits" de otras respuestas.

También podría repetir esto usando algo similar al método pivote para reducir aún más la complejidad. Reorganice la matriz en función de un punto de pivote (que será el máximo del lado izquierdo y el mínimo de la derecha; será trivial encontrar el máximo y el mínimo del conjunto completo mientras gira). Si el lado izquierdo del pivote tiene uno o más agujeros, recurra solo a ese lado; de lo contrario, recurrirá al otro lado. En cualquier punto en el que pueda determinar que solo hay un agujero, use el método XOR para encontrarlo (lo que debería ser más económico en general que continuar girando hasta una colección de dos elementos con un agujero conocido, que es el caso base para El algoritmo de pivote puro).

KeithS
fuente
¡Eso es ridículamente inteligente e increíble! Ahora, ¿puedes encontrar una manera de hacer esto con un número variable de agujeros? :-D
2

¿Cuál es el rango de números que encontrarás? Si ese rango no es muy grande, puede resolver esto con dos escaneos (tiempo lineal O (n)) usando una matriz con tantos elementos como números, intercambiando espacio por tiempo. Puede encontrar el rango dinámicamente con un escaneo más. Para reducir el espacio, puede asignar 1 bit a cada número, lo que le da 8 números de almacenamiento por byte.

Su otra opción que puede ser mejor para los primeros escenarios y que sería in situ en lugar de copiar memoria es modificar el orden de selección para salir antes si el mínimo encontrado en un pase de escaneo no es 1 más que el último minuto encontrado.

Peter Smith
fuente
1

No en realidad no. Dado que cualquier número aún no escaneado siempre podría ser uno que llene un "agujero" dado, no puede evitar escanear cada número al menos una vez y luego compararlo con sus posibles vecinos. Probablemente podría acelerar las cosas construyendo un árbol binario más o menos y luego atravesándolo de izquierda a derecha hasta que se encuentre un agujero, pero eso es esencialmente de la misma complejidad de tiempo que la clasificación, ya que es una clasificación. Y probablemente no se te ocurra nada más rápido que Timsort .

Pillmuncher
fuente
1
¿Estás diciendo que atravesar una lista es la misma complejidad de tiempo que ordenar?
maple_shaft
@maple_shaft: No, digo que construir un árbol binario a partir de datos aleatorios y luego recorrerlo de izquierda a derecha es equivalente a ordenar y luego recorrer de pequeño a grande.
pillmuncher
1

La mayoría de las ideas aquí no son más que solo ordenar. La versión de bitvector es Bucketsort simple. También se mencionó la ordenación del montón. Básicamente se reduce a elegir el algoritmo de clasificación correcto que depende de los requisitos de tiempo / espacio y también del rango y el número de elementos.

En mi opinión, el uso de una estructura de montón es probablemente la solución más general (un montón básicamente le proporciona los elementos más pequeños de manera eficiente sin una ordenación completa).

También podría analizar los enfoques que primero encuentran los números más pequeños y luego buscar cada número entero mayor que ese. O encuentra los 5 números más pequeños con la esperanza de que tengan un espacio.

Todos estos algoritmos tienen su fuerza dependiendo de las características de entrada y los requisitos del programa.

Gerenuk
fuente
0

Una solución que no utiliza almacenamiento adicional ni asume el ancho (32 bits) de los enteros.

  1. En una pasada lineal encuentra el número más pequeño. Vamos a llamar a esto "min". O (n) complejidad de tiempo.

  2. Elija un elemento pivote aleatorio y haga una partición de estilo de clasificación rápida.

  3. Si el pivote terminó en la posición = ("pivote" - "min"), entonces se repite en el lado derecho de la partición, de lo contrario se repite en el lado izquierdo de la partición. La idea aquí es que si no hay agujeros desde el principio, el pivote estaría en la posición ("pivote" - "min"), por lo que el primer agujero debería estar a la derecha de la partición y viceversa.

  4. El caso base es una matriz de 1 elemento y el agujero se encuentra entre este elemento y el siguiente.

La complejidad total esperada del tiempo de ejecución es O (n) (8 * n con las constantes) y el peor de los casos es O (n ^ 2). El análisis de complejidad temporal para un problema similar se puede encontrar aquí .

aufather
fuente
0

Creo que se me ocurrió algo que debería funcionar de manera general y eficiente si se garantiza que no tendrá duplicados * (sin embargo, debe ser extensible a cualquier número de agujeros y cualquier rango de enteros).

La idea detrás de este método es como la clasificación rápida, en la que encontramos un pivote y una partición a su alrededor, luego recurrimos en los lados con un agujero. Para ver qué lados tienen el agujero, encontramos los números más bajos y más altos, y los comparamos con el pivote y el número de valores en ese lado. Digamos que el pivote es 17 y el número mínimo es 11. Si no hay agujeros, debería haber 6 números (11, 12, 13, 14, 15, 16, 17). Si hay 5, sabemos que hay un agujero en ese lado y podemos recurrir solo en ese lado para encontrarlo. Tengo problemas para explicarlo más claramente que eso, así que tomemos un ejemplo.

15 21 10 13 18 16 22 23 24 20 17 11 25 12 14

Pivote:

10 13 11 12 14 |15| 21 18 16 22 23 24 20 17 25

15 es el pivote, indicado por tuberías ( ||). Hay 5 números en el lado izquierdo del pivote, como debería haber (15 - 10), y 9 en el derecho, donde debería haber 10 (25 - 15). Entonces recurrimos en el lado derecho; notaremos que el límite anterior era 15 en caso de que el hoyo sea adyacente (16).

[15] 18 16 17 20 |21| 22 23 24 25

Ahora hay 4 números en el lado izquierdo, pero debería haber 5 (21 - 16). Entonces repetimos allí, y nuevamente notaremos el límite anterior (entre paréntesis).

[15] 16 17 |18| 20 [21]

El lado izquierdo tiene los 2 números correctos (18 - 16), pero el derecho tiene 1 en lugar de 2 (20 - 18). Dependiendo de nuestras condiciones finales, podríamos comparar el número 1 con los dos lados (18, 20) y ver que 19 falta o se repite una vez más:

[18] |20| [21]

El lado izquierdo tiene un tamaño de cero, con un espacio entre el pivote (20) y el límite anterior (18), por lo que 19 es el agujero.

*: Si hay duplicados, probablemente podría usar un conjunto de hash para eliminarlos en el tiempo O (N), manteniendo el método general O (N), pero eso podría llevar más tiempo que usar algún otro método.

Kevin
fuente
1
No creo que el OP haya dicho nada sobre que solo haya un agujero. La entrada es una lista de números sin clasificar; podrían ser cualquier cosa. No está claro en su descripción cómo determinaría cuántos números "debería haber".
Caleb
@caleb No importa cuántos agujeros haya, simplemente no hay duplicados (que se pueden eliminar en O (N) con un conjunto de hash, aunque en la práctica pueden tener más sobrecarga que otros métodos). He intentado mejorar la descripción, ver si es mejor.
Kevin
Esto no es lineal, en mi opinión. Es más como (logN) ^ 2. En cada paso, gira el subconjunto de la colección que le interesa (la mitad del subconjunto anterior que ha identificado como que tiene el primer "agujero"), luego vuelve al lado izquierdo si tiene un "agujero", o el lado derecho si el lado izquierdo no lo hace. (logN) ^ 2 sigue siendo mejor que lineal; si N aumenta diez veces, solo toma el orden de 2 (log (N) -1) + 1 pasos más.
KeithS
@Keith: desafortunadamente, debe mirar todos los números en cada nivel para pivotarlos, por lo que tomará aproximadamente n + n / 2 + n / 4 + ... = 2n (técnicamente, 2 (nm)) comparaciones .
Kevin