arrays - data - linked list algorithm

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

Question

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 aparece 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.

Answer 1

1) filtro negativo y cero

2) Ordenar / distinto

3) Visita la matriz

Complejidad : O (N) u O (N * log (N))

usando Java8

public int solution(int[] A) {
            int result = 1;
    boolean found = false;
    A = Arrays.stream(A).filter(x -> x > 0).sorted().distinct().toArray();
    //System.out.println(Arrays.toString(A));
    for (int i = 0; i < A.length; i++) {
        result = i + 1;
        if (result != A[i]) {
            found = true;
            break;
        }
    }
    if (!found && result == A.length) {
        //result is larger than max element in array
        result++;
    }
    return result;
}

Answer 2

Aquí está mi respuesta escrita en Java:

Idea básica: 1- Pasa por la matriz tirando números positivos, ceros y negativos duplicados mientras suma el resto, obteniendo también el número positivo máximo y conserva los números positivos únicos en un mapa.

2- Calcule la suma como max * (max + 1) / 2.

3- Encuentra la diferencia entre las sumas calculadas en los pasos 1 y 2

4- Vuelva a conectar de 1 al mínimo de [diferencia de sumas, máx.] Y devuelva el primer número que no está en el mapa poblado en el paso 1.

public static int solution(int[] A) {
    if (A == null || A.length == 0) {
        throw new IllegalArgumentException();
    }

    int sum = 0;
    Map<Integer, Boolean> uniqueNumbers = new HashMap<Integer, Boolean>();
    int max = A[0];
    for (int i = 0; i < A.length; i++) {
        if(A[i] < 0) {
            continue;
        }
        if(uniqueNumbers.get(A[i]) != null) {
            continue;
        }
        if (A[i] > max) {
            max = A[i];
        }
        uniqueNumbers.put(A[i], true);
        sum += A[i];
    }
    int completeSum = (max * (max + 1)) /  2;
    for(int j = 1; j <= Math.min((completeSum - sum), max); j++) {
        if(uniqueNumbers.get(j) == null) { //O(1)
            return j;
        }
    }
    //All negative case
    if(uniqueNumbers.isEmpty()) {
        return 1;
    }
    return 0;
}

Answer 3

Aquí hay una respuesta en Java que no modifica la entrada y usa O (N) tiempo y N bits más una pequeña sobrecarga constante de memoria (donde N es el tamaño de la lista):

int smallestMissingValue(List<Integer> values) {
    BitSet bitset = new BitSet(values.size() + 1);
    for (int i : values) {
        if (i >= 0 && i <= values.size()) {
            bitset.set(i);
        }
    }
    return bitset.nextClearBit(0);
}

Answer 4

Aquí hay una solución O(N) simple 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. Asigne una matriz de N booleanos, inicializados a todos los false .
3. Para cada número X en la lista, si X es menor que N , establezca el elemento X''th de la matriz en true .
4. Escanee la matriz comenzando desde el índice 0 , buscando el primer elemento que es false . Si encuentra el primer false en el índice I , entonces I la respuesta. De lo contrario (es decir, cuando todos los elementos son true ) la respuesta es N

En la práctica, la "matriz de N booleanos" probablemente se codificaría como un "mapa de bits" o "conjunto de bits" representado como un byte o una matriz int . Esto normalmente utiliza menos espacio (según el lenguaje de programación) y permite que el escaneo del primer false se realice más rápidamente.

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

Supongamos que los N 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 que no está en la lista. Por lo tanto, el problema de encontrar el número más pequeño que falta debe reducirse 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 en true , y el paso 4 nos dice que el primer número "faltante" 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) contadores Xmax - Xmin 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, tiene que tener un tipo entero (al menos) de ceiling(log2(N)) bits.
• Para determinar el tamaño de la matriz, una clasificación de conteo debe hacer una pasada inicial a través de la lista para determinar Xmax y Xmin .
• El requisito mínimo de espacio en el peor de los casos es, por lo tanto, el 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.

Answer 5

Bien hecho Hormigas Aasma! Pensé en la respuesta durante unos 15 minutos y, de forma independiente, obtuve una respuesta similar a la tuya:

#define SWAP(x,y) { numerictype_t tmp = x; x = y; y = tmp; }
int minNonNegativeNotInArr (numerictype_t * a, size_t n) {
    int m = n;
    for (int i = 0; i < m;) {
        if (a[i] >= m || a[i] < i || a[i] == a[a[i]]) {
            m--;
            SWAP (a[i], a[m]);
            continue;
        }
        if (a[i] > i) {
            SWAP (a[i], a[a[i]]);
            continue;
        }
        i++;
    }
    return m;
}

m representa "la máxima salida posible actual dado lo que sé sobre las primeras i entradas y no asumiendo nada más sobre los valores hasta la entrada en m-1".

Este valor de m se devolverá solo si (a [i], ..., a [m-1]) es una permutación de los valores (i, ..., m-1). Por lo tanto, si a [i]> m o si a [i] <i o si a [i] == a [a [i]] sabemos que m es la salida incorrecta y debe ser al menos un elemento inferior. Así que disminuyendo m e intercambiando un [i] con a [m] podemos recurrir.

Si esto no es cierto pero a [i]> i sabiendo que a [i]! = A [a [i]] sabemos que al intercambiar un [i] con un [a [i]] aumentará la cantidad de elementos en su propio lugar.

De lo contrario, [i] debe ser igual a i, en cuyo caso podemos incrementar i sabiendo que todos los valores de hasta e incluyendo este índice son iguales a su índice.

La prueba de que esto no puede entrar en un ciclo infinito se deja como un ejercicio para el lector. :)

Answer 6

Bueno, si solo hay un número que falta en una lista de números, la manera más fácil de encontrar el número que falta es sumar la serie y restar cada valor de la lista. El valor final es el número que falta.

Answer 7

Como Stephen C inteligentemente señaló, la respuesta debe ser un número más pequeño que la longitud de la matriz. Entonces encontraría la respuesta por búsqueda binaria. Esto optimiza el peor de los casos (para que el entrevistador no pueda atraparlo en un escenario patológico "¿y si?"). En una entrevista, señale que está haciendo esto para optimizar el peor de los casos.

La forma de usar la búsqueda binaria es restar el número que está buscando de cada elemento de la matriz y comprobar si hay resultados negativos.

Answer 8

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 2 ⁶⁴ = 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 de 1 en 700,000. Y mis probabilidades de ser golpeado por un meteorito son de aproximadamente 1 en 10 billones. 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.

Answer 9

Como los números tienen 64 bits de longitud, podemos usar radix sort 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.

Answer 10

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.

Answer 11

El fragmento de Dafny de la respuesta de Hormigas muestra por qué el algoritmo in situ puede fallar. La condición previa requires que los valores de cada elemento no vayan más allá de los límites de la matriz.

method AntsAasma(A: array<int>) returns (M: int)
  requires A != null && forall N :: 0 <= N < A.Length ==> 0 <= A[N] < A.Length;
  modifies A; 
{
  // Pass 1, move every value to the position of its value
  var N := A.Length;
  var cursor := 0;
  while (cursor < N)
  {
    var target := A[cursor];
    while (0 <= target < N && target != A[target])
    {
        var new_target := A[target];
        A[target] := target;
        target := new_target;
    }
    cursor := cursor + 1;
  }

  // Pass 2, find first location where the index doesn''t match the value
  cursor := 0;
  while (cursor < N)
  {
    if (A[cursor] != cursor)
    {
      return cursor;
    }
    cursor := cursor + 1;
  }
  return N;
}

Pegue el código en el validador con y sin la cláusula forall ... para ver el error de verificación. El segundo error es el resultado de que el verificador no puede establecer una condición de terminación para el bucle de Pase 1. Demostrar esto se deja a alguien que entiende mejor la herramienta.

Answer 12

Gracias a egon, swilden y Stephen C por mi inspiración. Primero, conocemos los límites del valor objetivo porque no puede ser mayor que el tamaño de la lista. Además, una lista de 1 GB podría contener como máximo 134217728 (128 * 2 ^ 20) enteros de 64 bits.

Hashing parte
Propongo usar hashing para reducir drásticamente nuestro espacio de búsqueda. Primero, raíz cuadrada del tamaño de la lista. Para una lista de 1GB, eso es N = 11,586. Configure una matriz de enteros de tamaño N. Itere a través de la lista y tome la raíz cuadrada * de cada número que encuentre como su hash. En su tabla hash, incremente el contador para ese hash. Luego, itera a través de tu tabla hash. El primer segmento que encuentre que no sea igual a su tamaño máximo define su nuevo espacio de búsqueda.

Parte de mapa de bits
Ahora configure un mapa de bits regular igual al tamaño de su nuevo espacio de búsqueda, y repita de nuevo a través de la lista de fuentes, completando el mapa de bits a medida que encuentre cada número en su espacio de búsqueda. Cuando haya terminado, el primer bit no ajustado en su mapa de bits le dará su respuesta.

Esto se completará en el tiempo O (n) y en el espacio O (sqrt (n)).

(* Podría usar algo como cambiar de bit para hacer esto de manera mucho más eficiente, y simplemente variar la cantidad y el tamaño de los cubos en consecuencia).

Answer 13

Me gusta el apprac de "adivinar cero". Si los números fueron aleatorios, cero es altamente probable. Si el "examinador" establece una lista no aleatoria, agregue una y adivine de nuevo:

LowNum=0
i=0
do forever {
  if i == N then leave /* Processed entire array */
  if array[i] == LowNum {
     LowNum++
     i=0
     }
   else {
     i++
   }
}
display LowNum

El peor caso es n * N con n = N, pero en la práctica n es muy probable que sea un número pequeño (por ejemplo, 1)

Answer 14

No estoy seguro de si tengo la pregunta. Pero si para la lista 1,2,3,5,6 y el número que falta es 4, entonces el número que falta se puede encontrar en O (n) por: (n + 2) (n + 1) / 2- (n + 1) n / 2

EDIT: lo siento, creo que estaba pensando demasiado rápido anoche. De todos modos, la segunda parte debería reemplazarse por suma (lista), que es donde viene O (n). La fórmula revela la idea detrás de esto: para n enteros secuenciales, la suma debe ser (n + 1) * n / 2. Si falta un número, la suma sería igual a la suma de (n + 1) enteros secuenciales menos el número faltante.

Gracias por señalar el hecho de que estaba poniendo algunas piezas intermedias en mi mente.

Answer 15

Ordene la lista, mire los elementos primero y segundo, y comience a subir hasta que haya un espacio.

Answer 16

Para ilustrar una de las trampas del pensamiento O(N) , aquí hay un algoritmo O(N) 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"

Answer 17

Para un método de espacio eficiente y todos los valores son distintos, puede hacerlo en el espacio O( k ) y en el 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. establecer U = N; L=0 U = N; L=0
2. Primero particione el espacio numérico en k regiones. Me gusta esto:
   • 0->(1/k)*(UL) + L , 0->(2/k)*(UL) + L , 0->(3/k)*(UL) + L ... 0->(UL) + L
3. Encuentra cuántos números ( count{i} ) hay en cada región. ( N*k pasos)
4. Encuentra la primera región ( h ) que no está llena. Eso significa count{h} < upper_limit{h} . ( k pasos)
5. si h - count{h-1} = 1 tienes tu respuesta
6. establecer U = count{h}; L = count{h-1} U = count{h}; L = count{h-1}
7. Ir a 2

esto se puede mejorar usando hashing (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) * (UL) ''
3. inc count{j} usando j = (number - L)/k (if L < number < U)
4. encuentra la primera región ( h ) que no tiene k elementos en ella
5. si count{h} = 1 h es tu respuesta
6. establecer U = maximum value in region h L = minimum value in region h

Esto se ejecutará en O(log(N)*N) .

Answer 18

Podríamos usar una tabla hash para contener los números. Una vez que todos los números estén listos, ejecute un contador desde 0 hasta que encontremos el más bajo. Un hash razonablemente bueno se almacenará en tiempo constante y se recuperará en tiempo constante.

for every i in X         // One scan Θ(1)
   hashtable.put(i, i);  // O(1)

low = 0;

while (hashtable.get(i) <> null)   // at most n+1 times
   low++;

print low;

El peor caso si hay n elementos en la matriz, y son {0, 1, ... n-1} , en cuyo caso, la respuesta se obtendrá en n , manteniéndola O(n) .

Answer 19

Puede hacerlo en O (n) tiempo y O (1) espacio adicional, aunque el factor oculto es bastante grande. Esta no es una forma práctica de resolver el problema, pero podría ser interesante de todos modos.

Para cada entero sin signo de 64 bits (en orden ascendente) itere sobre la lista hasta que encuentre el entero del objetivo o llegue al final de la lista. Si llega al final de la lista, el entero objetivo es el entero más pequeño que no está en la lista. Si llega al final de los enteros de 64 bits, cada entero de 64 bits está en la lista.

Aquí está como una función de Python:

def smallest_missing_uint64(source_list):
    the_answer = None

    target = 0L
    while target < 2L**64:

        target_found = False
        for item in source_list:
            if item == target:
                target_found = True

        if not target_found and the_answer is None:
            the_answer = target

        target += 1L

    return the_answer

Esta función es deliberadamente ineficiente para mantenerlo O (n). Tenga en cuenta especialmente que la función sigue comprobando los enteros objetivo incluso después de que se haya encontrado la respuesta. Si la función regresó tan pronto como se encontró la respuesta, la cantidad de veces que se ejecutó el bucle externo estaría limitada por el tamaño de la respuesta, que está limitada por n. Ese cambio haría que el tiempo de ejecución sea O (n ^ 2), aunque sería mucho más rápido.

Answer 20

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

Answer 21

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")

Answer 22

Un conjunto no ordenado se puede utilizar para almacenar todos los números positivos, y luego podemos iterar de 1 a la longitud de unordered_set, y ver el primer número que no ocurre.

int firstMissingPositive(vector<int>& nums) {

    unordered_set<int> fre;
    // storing each positive number in a hash.
    for(int i = 0; i < nums.size(); i +=1)
    {
        if(nums[i] > 0)
            fre.insert(nums[i]);
     }

    int i = 1;
    // Iterating from 1 to size of the set and checking 
    // for the occurrence of ''i''

    for(auto it = fre.begin(); it != fre.end(); ++it)
    {
        if(fre.find(i) == fre.end())
            return i;
        i +=1;
    }

    return i;
}

Answer 23

 int i = 0;
            while ( i < Array.Length)
            {

                if (Array[i] == i + 1)
                {
                    i++;
                }

                if (i < Array.Length)
                {
                    if (Array[i] <= Array.Length)
                    {//SWap

                        int temp = Array[i];
                        int AnoTemp = Array[temp - 1];
                        Array[temp - 1] = temp;
                        Array[i] = AnoTemp;

                    }
                    else
                       i++;



                }
            }

            for (int j = 0; j < Array.Length; j++)
            {
                if (Array[j] > Array.Length)
                {
                    Console.WriteLine(j + 1);
                    j = Array.Length;
                }
                else
                    if (j == Array.Length - 1)
                        Console.WriteLine("Not Found !!");

            }
        }

Answer 24

def solution(A):

index = 0
target = []
A = [x for x in A if x >=0]

if len(A) ==0:
    return 1

maxi = max(A)
if maxi <= len(A):
    maxi = len(A)

target = [''X'' for x in range(maxi+1)]
for number in A:
    target[number]= number

count = 1
while count < maxi+1:
    if target[count] == ''X'':
        return count
    count +=1
return target[count-1] + 1

Obtuve el 100% de la solución anterior.