Dada una lista desordenada de enteros, devuelva un valor no presente en la lista

Question

Tengo un problema de algoritmo que encontré en el trabajo pero no he podido encontrar una solución satisfactoria para. Busqué este foro y lo más cercano que he llegado al mismo problema es How to find a duplicate element in an array of shuffled consecutive integers?.

Tengo una lista de N elementos de enteros que pueden contener los elementos 1-M (M> N), además, la lista no está ordenada. Quiero una función que tomará esta lista como entrada y devolverá un valor en el rango 1-M que no está presente en la lista. La lista no contiene duplicados. Tenía la esperanza de una solución de O (n), con a cabo utilizando espacio actualización adicional: función no se puede cambiar la lista original L

por ejemplo N = 5 M = 10 la lista (L): 1, 2, 4, 8, 3 entonces f (L) = 5 para ser honesta no me importa si devuelve un elemento distinto de 5, con tal de que cumpla los contraints anteriormente

La única solución que he encontrado hasta el momento está usando una matriz adicional de M elementos. Recorre la lista de entrada y establece los elementos de matriz correspondientes en 1 si está presente en la lista. Luego, vuelva a iterar sobre esta lista y regrese el índice del primer elemento con el valor 0. Como puede ver, esto usa un espacio o (M) adicional y tiene una complejidad 2 * o (N). Cualquier ayuda sería apreciada.

Gracias por la ayuda de todos. La comunidad de desbordamiento de pila es definitivamente muy útil. Para dar a cada uno un poco más de contexto del problema que estoy tratando de resolver. Tengo un conjunto de tokens M que doy a algunos clientes (uno por cliente). Cuando un cliente termina con la ficha, vuelve a mi pila. Como puede ver, el orden original que le doy al cliente es un token ordenado.
de modo M = 3         Tokens
cliente1: 1                 < 2,3>
client2: 2                 < 3>
retorno cliente1: 1     < 1,3>
cliente 3: 3             < 1>
Ahora la cuestión está dando client4 token de 1. En esta etapa podría dar cliente 4 token 2 y ordenar la lista. No estoy seguro si eso ayudaría. En cualquier caso, si se me ocurre una buena solución limpia, me aseguraré de publicarlo
Me acabo de dar cuenta de que podría haber confundido a todos. No tengo la lista de tokens gratis cuando me llaman. Podría mantener estáticamente una lista así, pero preferiría no

Answer 1

puede tener O (N) tiempo y espacio. Puede estar seguro de que hay un elemento ausente en 1..N + 1, por lo tanto, cree una matriz de N + 1 elementos e ignore los números mayores que N + 1.

Si M es grande en comparación con N, digamos M> 2N, genere un número aleatorio en 1..M y verifique si no está en la lista en O (N) tiempo, O (1) espacio. La probabilidad de que encuentre una solución en una sola pasada es al menos 1/2, y por lo tanto (distribución geométrica) el número esperado de pases es constante, la complejidad promedio O (N).

Si M es N + 1 o N + 2, utilice el método descrito here.

Answer 2

¿Se puede hacer algo así como un tipo de conteo? Cree una matriz de tamaño (M-1), luego recorra la lista una vez (N) y cambie el elemento de la matriz indexado en i-1 a uno. Después de pasar una vez por N, busque 0 -> (M-1) hasta que encuentre la primera matriz con un valor cero.

Debería yo O (N + M).

Matriz L de tamaño (M-1): [0 = 0, 1 = 0, 2 = 0, 3 = 0, 4 = 0, 5 = 0, 6 = 0, 7 = 0, 8 = 0 , 9 = 0]

Después de recorrer los N elementos: [0 = 1, 1 = 1, 2 = 1, 3 = 1, 4 = 0, 5 = 0, 6 = 0, 7 = 1, 8 = 0, 9 = 0]

Buscar array 0 -> (M-1) encuentra índice 4 es cero, por lo tanto, 5 (4 + 1) es el primer número entero no en L.

Answer 3

Puedes dividir y conquistar. Básicamente dado el rango 1..m, haga un intercambio de estilo de quicksort con m/2 como pivote. Si hay menos de m/2 elementos en la primera mitad, entonces hay un número que falta y lo encuentra iterativamente. De lo contrario, falta un número en la segunda mitad. Complejidad: n + n/2 + n/4 ... = O (n)

def findmissing(x, startIndex, endIndex, minVal, maxVal): 
    pivot = (minVal+maxVal)/2 
    i=startIndex 
    j=endIndex 
    while(True): 
     while((x[i] <= pivot) and (i<j)): 
      i+=1 
     if i>=j: 
      break 
     while((x[j] > pivot) and (i<j)): 
      j+=1 
     if i>=j: 
      break 
     swap(x,i,j) 
    k = findlocation(x,pivot) 
    if (k-startIndex) < (pivot-minVal): 
     findmissing(x,startIndex, k, minVal, pivot) 
    else: 
     findmissing(x, k+1, endIndex, pivot+1, maxVal) 

no he implementado la condición final que voy a dejar a usted.

Answer 4

Después de leer su actualización supongo que lo está haciendo más complejo. En primer lugar, permítanme enumerar abajo de lo que recibo de su pregunta

• Yoou necesitan dar un token para el cliente, independientemente de su orden, citando a su puesto original

por ejemplo N = 5 M = 10 Lista (L): 1, 2, 4, 8, 3 luego f (L) = 5 Ser honesto no me importa si devuelve un elemento que no sea 5, tan largo ya que cumple con las restricciones arriba

• En segundo lugar, ya está manteniendo una lista de "M" tokens
• cliente es ir a buscar la ficha y después de usarlo regresar de nuevo a usted

Teniendo en cuenta estos 2 puntos, ¿por qué no se implementa una TokenPool?

• implementar su lista M en base a una cola de
• Cada vez que un cliente pide un token, buscar un token de la cola es decir, sacarlo de cola. Con este método, tu cola siempre mantendrá esos tokens que no se regalan. lo está haciendo O (1)
• Cada vez que un cliente finaliza con el token, se lo devolverá. Agréguelo a la cola. De nuevo O (1).

En la implementación completa, no tendría que recorrer ninguna de las listas. Todo lo que tienes que hacer es generar el token e insertarlo en la cola.