Encuentre un “agujero” en una lista de números

14

¿Cuál es la forma más rápida de encontrar el primer entero (el 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 repasar la lista, ¿hay alguna manera mejor?

    
pregunta Fabian Zeindl 24.04.2012 - 18:27

8 respuestas

29

Suponiendo que te refieres a "entero" cuando dices "número", puedes usar un vector de bits de tamaño 2 ^ n, donde n es el número de elementos (por ejemplo, tu rango incluye enteros entre 1 y 256, entonces puedes usar un bitvector de 256 bits, o 32 bytes,). Cuando se encuentre con un número entero en la posición n de su rango, establezca el enésimo bit.

Cuando termines de enumerar la colección de enteros, recorres los bits en tu bitvector, buscando la posición de cualquier conjunto de bits 0. Ahora coinciden con la posición n de los números enteros que faltan.

Esto es O (2 * N), por lo tanto, O (N) y probablemente más eficiente en memoria que la clasificación completa.

    
respondido por el JasonTrue 24.04.2012 - 18:45
4

Si primero clasifica la lista completa, garantiza el peor tiempo de ejecución. Además, su elección del algoritmo de clasificación es fundamental.

Así es como abordaría este problema:

  1. Use una ordenación de pila , centrándose en los elementos más pequeños de la lista.
  2. Después de cada intercambio, vea si tiene un hueco.
  3. Si encuentra un espacio vacío, entonces return : ha encontrado su respuesta.
  4. Si no encuentra un hueco, continúe con el intercambio.

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

    
respondido por el Jim G. 24.04.2012 - 18:53
3

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 posterior, 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 menos que la cardinalidad del conjunto, solo hay un "agujero" para que pueda usar XOR.
  • Inicializa una variable entera X a cero.
  • Para cada entero de min a max inclusive, XOR ese valor con X y almacena el resultado en X.
  • Ahora haga XOR en cada entero en la matriz con X, almacenando cada resultado sucesivo en X como antes.
  • Cuando hayas terminado, X será el valor de tu "agujero".

Esto se ejecutará aproximadamente en el tiempo 2N similar a la solución bitvector, pero requiere menos espacio de memoria para cualquier N > sizeof (int). Sin embargo, si la matriz tiene varios "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 otro método, como los enfoques "pivote" o "bitvector" de otras respuestas.

También puedes repetir esto usando algo similar al método de pivote para reducir aún más la complejidad. Reorganice la matriz según 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 de la matriz completa mientras se gira). Si el lado izquierdo del pivote tiene uno o más orificios, haga retroceso en ese lado solamente; De lo contrario, recuéstate al otro lado. En cualquier punto donde pueda determinar que solo hay un orificio, use el método XOR para encontrarlo (que debería ser más económico en general que continuar girando hasta una colección de dos elementos con un orificio conocido, que es el caso base para el algoritmo de pivote puro).

    
respondido por el KeithS 24.04.2012 - 19:25
2

¿Cuál es el rango de números que encontrarás? Si ese rango no es muy grande, puede resolverlo con dos exploraciones (tiempo lineal O (n)) utilizando una matriz con tantos elementos como tenga números, intercambiando espacio por tiempo. Podrías 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 otorga 8 números de almacenamiento por byte.

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

    
respondido por el Peter Smith 24.04.2012 - 18:41
1

No, en realidad no. Dado que cualquier número aún no escaneado puede ser siempre 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 se está clasificando. Y probablemente no se te ocurra algo más rápido que Timsort .

    
respondido por el pillmuncher 24.04.2012 - 18:52
1

La mayoría de las ideas aquí no son más que simples clasificaciones. La versión de bitvector es simple Bucketsort. También se mencionó el tipo de pila. 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 número de elementos.

En mi opinión, usar una estructura de montón es probablemente la solución más general (un montón básicamente te da los elementos más pequeños eficientemente sin una clasificación completa).

También podría analizar enfoques que encuentren primero los números más pequeños y luego escanear para cada entero más grande que eso. O encuentra los 5 números más pequeños con la esperanza de que haya un hueco.

Todos estos algoritmos tienen su fuerza en función de las características de entrada y los requisitos del programa.

    
respondido por el Gerenuk 26.04.2012 - 09:40
0

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

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

  2. Elija un elemento de pivote aleatorio y haga una partición de estilo quicksort.

  3. Si el pivote terminó en la posición = ("pivote" - "min"), recurra en el lado derecho de la partición, de lo contrario recurra 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 ("pivote" - "min") th posición, 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 del tiempo total de ejecución esperado es O (n) (8 * n con las constantes) y el peor de los casos es O (n ^ 2). El análisis de la complejidad del tiempo para un problema similar se puede encontrar aquí .

    
respondido por el aufather 25.04.2012 - 17:39
0

Creo que se me ha ocurrido algo que debería funcionar de manera general y eficiente si tiene la garantía de no tener duplicados * (sin embargo, debería ser extensible a cualquier número de orificios y cualquier rango de enteros).

La idea detrás de este método es como una ordenación rápida, en la que encontramos un pivote y una partición a su alrededor, luego retrocedemos en los lados con un agujero. Para ver qué lados tienen el orificio, 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 ayudarnos solo en ese lado para encontrarlo. Tengo problemas para explicarlo más claramente que eso, así que vamos a dar 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). Así que nos ocupamos en el lado derecho; notaremos que el límite anterior era 15 en caso de que el agujero esté adyacente a él (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). Por lo tanto, 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 falta 19 o repetir 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 orificio.

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

    
respondido por el Kevin 25.04.2012 - 16:35

Lea otras preguntas en las etiquetas