Pregunta Encuentre el entero más pequeño que no está en una lista


Una interesante pregunta de entrevista que un colega mío usa:

Supongamos que se le proporciona una lista muy larga y sin clasificar de enteros de 64 bits sin signo. ¿Cómo encontraría el entero no negativo más pequeño que no ocurrir en la lista?

SEGUIMIENTO: Ahora que se ha propuesto la solución obvia por clasificación, ¿puede hacerlo más rápido que O (n log n)?

SEGUIMIENTO: su algoritmo debe ejecutarse en una computadora con, digamos, 1GB de memoria

ACLARACIÓN: La lista está en RAM, aunque podría consumir una gran cantidad de ella. Le dan el tamaño de la lista, digamos N, de antemano.


73
2017-10-19 03:44


origen


Respuestas:


Si la estructura de datos puede mutarse en su lugar y admite acceso aleatorio, puede hacerlo en tiempo O (N) y en O (1) espacio adicional. Simplemente recorra el conjunto secuencialmente y para cada índice escriba el valor del índice en el índice especificado por valor, coloque recursivamente cualquier valor en esa ubicación en su lugar y arroje valores> N. Luego, vuelva a recorrer el conjunto buscando el lugar donde el valor no coincide con el índice; ese es el valor más pequeño que no está en la matriz. Esto resulta en la mayoría de las comparaciones de 3N y solo usa unos pocos valores de espacio temporal.

# Pass 1, move every value to the position of its value
for cursor in range(N):
    target = array[cursor]
    while target < N and target != array[target]:
        new_target = array[target]
        array[target] = target
        target = new_target

# Pass 2, find first location where the index doesn't match the value
for cursor in range(N):
    if array[cursor] != cursor:
        return cursor
return N

105
2017-10-20 06:14



Aquí hay un simple O(N) solución que usa O(N) espacio. Asumo que estamos restringiendo la lista de entrada a números no negativos y que queremos encontrar el primer número no negativo que no está en la lista.

  1. Encuentra la longitud de la lista; digamos que es N.
  2. Asignar una matriz de N booleanos, inicializados a todos false.
  3. Para cada número X en la lista, si X es menos que N, selecciona el X'th elemento de la matriz para true.
  4. Escanee la matriz comenzando desde el índice 0, buscando el primer elemento que es false. Si encuentras el primero false en el índice I, entonces I es la respuesta. De lo contrario (es decir, cuando todos los elementos están true) la respuesta es N.

En la práctica, la "variedad de N booleanos "probablemente se codificaría como un" mapa de bits "o" conjunto de bits "representado como un byte o int formación. Normalmente, esto utiliza menos espacio (según el lenguaje de programación) y permite el escaneo del primer false para hacer más rápido.


Así es como / por qué funciona el algoritmo.

Supongamos que el N los números en la lista no son distintos, o que uno o más de ellos es mayor que N. Esto significa que debe haber al menos un número en el rango 0 .. N - 1 eso no está en la lista. Entonces, el problema de encontrar el número más pequeño que falta se debe reducir al problema de encontrar el número más pequeño que falta menos que N. Esto significa que no necesitamos hacer un seguimiento de los números que son mayores o iguales a N ... porque no serán la respuesta.

La alternativa al párrafo anterior es que la lista es una permutación de los números de 0 .. N - 1. En este caso, el paso 3 establece todos los elementos de la matriz true, y el paso 4 nos dice que el primer número "perdido" es N.


La complejidad computacional del algoritmo es O(N) con una constante de proporcionalidad relativamente pequeña. Hace dos pasos lineales a través de la lista, o solo una pasada si se sabe que la longitud de la lista comienza. No es necesario representar la retención de toda la lista en la memoria, por lo que el uso de memoria asintótica del algoritmo es justo lo que se necesita para representar la matriz de booleanos; es decir O(N) bits.

(Por el contrario, los algoritmos que se basan en la clasificación o partición en memoria suponen que puede representar toda la lista en la memoria. En la forma en que se formuló la pregunta, esto requeriría O(N) Palabras de 64 bits.)


@Jorn comenta que los pasos 1 a 3 son una variación del tipo de conteo. En cierto sentido, él tiene razón, pero las diferencias son significativas:

  • Una clasificación de conteo requiere una matriz de (al menos) Xmax - Xmin contadores donde Xmax es el número más grande en la lista y Xmin es el número más pequeño en la lista. Cada contador debe poder representar N estados; es decir, asumiendo una representación binaria, debe tener un tipo entero (al menos) ceiling(log2(N)) bits.
  • Para determinar el tamaño de la matriz, una clasificación de conteo debe hacer un pase inicial a través de la lista para determinar Xmax y Xmin.
  • Por lo tanto, el requisito mínimo de espacio en el peor de los casos es ceiling(log2(N)) * (Xmax - Xmin) bits.

Por el contrario, el algoritmo presentado anteriormente simplemente requiere N bits en el peor y los mejores casos.

Sin embargo, este análisis lleva a la intuición de que si el algoritmo realizara un pase inicial a través de la lista buscando un cero (y contando los elementos de la lista si fuera necesario), daría una respuesta más rápida sin usar espacio si encontrara el cero. Definitivamente vale la pena hacer esto si hay una alta probabilidad de encontrar al menos un cero en la lista. Y este pase adicional no cambia la complejidad general.


EDITAR: He cambiado la descripción del algoritmo para usar "array of booleans" ya que las personas aparentemente encontraron mi descripción original usando bits y bitmaps para ser confusa.


85
2017-10-19 04:23



Como el OP ahora ha especificado que la lista original está contenida en la RAM y que la computadora tiene solo, digamos, 1GB de memoria, me voy a quedar en una extremidad y predigo que la respuesta es cero.

1 GB de RAM significa que la lista puede tener un máximo de 134,217,728 números. Pero hay 264 = 18,446,744,073,709,551,616 números posibles. Entonces la probabilidad de que cero esté en la lista es 1 en 137,438,953,472.

Por el contrario, mis probabilidades de ser alcanzado por un rayo este año son 1 en 700,000. Y mis probabilidades de ser golpeado por un meteorito son aproximadamente 1 en 10 trillones. Así que tengo una probabilidad diez veces mayor de escribir en un diario científico debido a mi muerte prematura por parte de un objeto celestial que cuando la respuesta no es cero.


13
2017-10-19 04:33



Como se señaló en otras respuestas, puede hacer una ordenación y luego escanear hasta encontrar un espacio.

Puede mejorar la complejidad algorítmica a O (N) y mantener el espacio O (N) utilizando una QuickSort modificada donde elimine las particiones que no son candidatos potenciales para contener el espacio.

  • En la primera fase de partición, eliminar duplicados.
  • Una vez que la partición está completa mira el número de elementos en la partición inferior
  • ¿Este valor es igual al valor utilizado para crear la partición?
    • Si es así, implica que la brecha está en la partición superior.
      • Continúe con la orden rápida, ignorando la partición inferior
    • De lo contrario, la brecha está en la partición inferior
      • Continúe con la orden rápida, ignorando la partición superior

Esto ahorra una gran cantidad de cálculos.


10
2017-10-19 04:12



Como los números son todos de 64 bits de largo, podemos usar clase de radix en ellos, que es O (n). Ordenarlos, luego escanearlos hasta que encuentre lo que está buscando.

si el número más pequeño es cero, escanee hacia adelante hasta que encuentre un espacio. Si el número más pequeño no es cero, la respuesta es cero.


8
2017-10-19 04:06



Para ilustrar uno de los peligros de O(N) pensando, aquí hay una O(N) Algoritmo que usa O(1) espacio.

for i in [0..2^64):
  if i not in list: return i

print "no 64-bit integers are missing"

8
2017-10-19 05:38



Para un método de espacio eficiente y todos los valores son distintos, puedes hacerlo en el espacio O( k ) y tiempo O( k*log(N)*N ). Es eficiente en el uso del espacio y no hay datos en movimiento y todas las operaciones son elementales (sumar restas).

  1. conjunto U = N; L=0
  2. Primero particione el espacio numérico en k regiones. Me gusta esto:
    • 0->(1/k)*(U-L) + L, 0->(2/k)*(U-L) + L, 0->(3/k)*(U-L) + L ... 0->(U-L) + L
  3. Encuentra cuántos números (count{i}) están en cada región. (N*k pasos)
  4. Encuentra la primera región (h) que no está lleno. Eso significa count{h} < upper_limit{h}. (k pasos)
  5. Si h - count{h-1} = 1 tienes tu respuesta
  6. conjunto U = count{h}; L = count{h-1}
  7. Ir a 2

esto se puede mejorar usando hash (gracias a Nic esta idea).

  1. mismo
  2. Primero particione el espacio numérico en k regiones. Me gusta esto:
    • `L + (i / k) -> L + (i + 1 / k) * (U-L) '
  3. inc count{j} utilizando j = (number - L)/k  (if L < number < U)
  4. encontrar la primera región (h) que no tiene k elementos en ella
  5. Si count{h} = 1 h es tu respuesta
  6. conjunto U = maximum value in region h  L = minimum value in region h

Esto correrá en O(log(N)*N).


5
2017-10-19 07:42



Simplemente los clasificaba y luego ejecutaba la secuencia hasta que encontraba un espacio (incluyendo el espacio al comienzo entre cero y el primer número).

En términos de un algoritmo, algo como esto lo haría:

def smallest_not_in_list(list):
    sort(list)
    if list[0] != 0:
        return 0
    for i = 1 to list.last:
        if list[i] != list[i-1] + 1:
            return list[i-1] + 1
    if list[list.last] == 2^64 - 1:
        assert ("No gaps")
    return list[list.last] + 1

Por supuesto, si tiene mucha más memoria que CPU grunt, podría crear una máscara de bits de todos los valores posibles de 64 bits y simplemente establecer los bits para cada número en la lista. Luego busca el primer 0 bit en esa máscara de bits. Eso lo convierte en una operación de O (n) en términos de tiempo, pero bastante costoso en términos de requisitos de memoria :-)

Dudo que puedas mejorar en O (n) ya que no veo una manera de hacerlo que no implique mirar cada número al menos una vez.

El algoritmo para eso estaría en la línea de:

def smallest_not_in_list(list):
    bitmask = mask_make(2^64) // might take a while :-)
    mask_clear_all (bitmask)
    for i = 1 to list.last:
        mask_set (bitmask, list[i])
    for i = 0 to 2^64 - 1:
        if mask_is_clear (bitmask, i):
            return i
    assert ("No gaps")

3
2017-10-19 03:48