La pregunta fácil de la entrevista se hizo más difícil: dados los números 1..100, encuentre los números faltantes dados exactamente k faltan

1146

Tuve una interesante experiencia de entrevista de trabajo hace un tiempo. La pregunta comenzó realmente fácil:

Q1 : Tenemos una bolsa que contenía los números 1, 2, 3, ..., 100. Cada número aparece exactamente una vez, por lo que hay 100 números. Ahora se saca un número al azar de la bolsa. Encuentre el número perdido.

He escuchado esta pregunta de la entrevista antes, por supuesto, así que rápidamente respondí en la línea de:

A1 : Bueno, la suma de los números 1 + 2 + 3 + … + Nes (N+1)(N/2)(ver Wikipedia: suma de series aritméticas ). Para N = 100, la suma es 5050.

Por lo tanto, si todos los números están presentes en la bolsa, la suma será exactamente 5050. Como falta un número, la suma será menor que esto, y la diferencia es ese número. Entonces podemos encontrar ese número faltante en el O(N)tiempo y el O(1)espacio.

En este punto, pensé que lo había hecho bien, pero de repente la pregunta tomó un giro inesperado:

P2 : Eso es correcto, pero ahora, ¿cómo haría esto si faltan DOS números?

Nunca antes había visto / escuchado / considerado esta variación, así que entré en pánico y no pude responder la pregunta. El entrevistador insistió en conocer mi proceso de pensamiento, por lo que mencioné que quizás podamos obtener más información comparándolo con el producto esperado, o tal vez haciendo un segundo pase después de haber reunido alguna información del primer pase, etc., pero realmente solo estaba disparando en la oscuridad en lugar de tener un camino claro hacia la solución.

El entrevistador intentó alentarme diciendo que tener una segunda ecuación es, de hecho, una forma de resolver el problema. En este punto, estaba un poco molesto (por no saber la respuesta de antemano), y le pregunté si esta es una técnica de programación general (léase: "útil"), o si es solo una respuesta truco / gotcha.

La respuesta del entrevistador me sorprendió: puedes generalizar la técnica para encontrar 3 números faltantes. De hecho, puede generalizarlo para encontrar k números faltantes.

Qk : Si faltan exactamente k números de la bolsa, ¿cómo lo encontrarían eficientemente?

Esto fue hace unos meses, y todavía no podía entender qué es esta técnica. Obviamente hay un Ω(N)tiempo límite inferior ya que debemos analizar todos los números al menos una vez, pero el entrevistador insistido en que el TIEMPO y ESPACIO complejidad de la técnica de la solución (menos la O(N)exploración de entradas de tiempo) se define en k no N .

Entonces la pregunta aquí es simple:

  • ¿Cómo resolverías la Q2 ?
  • ¿Cómo resolverías la Q3 ?
  • ¿Cómo resolverías Qk ?

Aclaraciones

  • Generalmente hay N números de 1 .. N , no solo 1..100.
  • No estoy buscando la solución obvia basada en conjuntos, por ejemplo, utilizando un conjunto de bits , codificando la presencia / ausencia de cada número por el valor de un bit designado, por lo tanto, utilizando O(N)bits en espacio adicional. No nos podemos permitir ningún espacio adicional proporcional a N .
  • Tampoco estoy buscando el enfoque obvio de ordenar primero. Vale la pena mencionar este y el enfoque basado en conjuntos en una entrevista (son fáciles de implementar y, dependiendo de N , pueden ser muy prácticos). Estoy buscando la solución del Santo Grial (que puede o no ser práctica de implementar, pero sin embargo tiene las características asintóticas deseadas).

De nuevo, por supuesto, debe escanear la entrada O(N), pero solo puede capturar una pequeña cantidad de información (definida en términos de k no N ), y luego debe encontrar los k números que faltan de alguna manera.

poligenelubricantes
fuente
77
@polygenelubricants Gracias por las aclaraciones. "Estoy buscando un algoritmo que utilice el tiempo O (N) y el espacio O (K) donde K es el recuento de números ausentes" habría sido claro desde el principio ;-)
Dave O.
77
Debe precisar, en la declaración de Q1, que no puede acceder a los números en orden. Esto probablemente te parezca obvio, pero nunca he oído hablar de la pregunta y el término "bolsa" (que también significa "multiset") fue algo confuso.
Jérémie
77
Lea lo siguiente ya que las respuestas proporcionadas aquí son ridículas: stackoverflow.com/questions/4406110/…
18
La solución de sumar los números requiere espacio log (N) a menos que considere que el requisito de espacio para un número entero ilimitado es O (1). Pero si permite enteros ilimitados, entonces tiene tanto espacio como desee con solo un entero.
Udo Klein
3
Por cierto, una solución alternativa bastante buena para Q1 podría ser calcular XORtodos los números desde 1hasta n, y luego obtener el resultado con todos los números en la matriz dada. Al final tienes tu número faltante. En esta solución, no necesita preocuparse por el desbordamiento como en el resumen.
sbeliakov

Respuestas:

590

Aquí hay un resumen del enlace de Dimitris Andreou .

Recuerde la suma de las i-ésimas potencias, donde i = 1,2, .., k. Esto reduce el problema de resolver el sistema de ecuaciones.

a 1 + a 2 + ... + a k = b 1

a 1 2 + a 2 2 + ... + a k 2 = b 2

...

a 1 k + a 2 k + ... + a k k = b k

Usando las identidades de Newton , saber b i permite calcular

c 1 = a 1 + a 2 + ... a k

c 2 = a 1 a 2 + a 1 a 3 + ... + a k-1 a k

...

c k = a 1 a 2 ... a k

Si expande el polinomio (xa 1 ) ... (xa k ) los coeficientes serán exactamente c 1 , ..., c k - vea las fórmulas de Viète . Dado que cada factor polinómico es único (el anillo de polinomios es un dominio euclidiano ), esto significa que i está determinado de manera única, hasta la permutación.

Esto termina con una prueba de que recordar poderes es suficiente para recuperar los números. Para k constante, este es un buen enfoque.

Sin embargo, cuando k varía, el enfoque directo de la computación c 1 , ..., c k es prohibitivamente costoso, ya que, por ejemplo, c k es el producto de todos los números faltantes, ¡magnitud n! / (Nk) !. Para superar esto, realice cálculos en el campo Z q , donde q es primo tal que n <= q <2n, existe por el postulado de Bertrand . No es necesario cambiar la prueba, ya que las fórmulas aún se mantienen y la factorización de polinomios sigue siendo única. También necesita un algoritmo para la factorización sobre campos finitos, por ejemplo, el de Berlekamp o Cantor-Zassenhaus .

Pseudocódigo de alto nivel para k constante:

  • Calcular i-ésima potencia de números dados
  • Resta para obtener sumas de i-ésima potencia de números desconocidos. Llame las sumas b i .
  • Utilice las identidades de Newton para calcular los coeficientes de b i ; llámalos c i . Básicamente, c 1 = b 1 ; c 2 = (c 1 b 1 - b 2 ) / 2; ver Wikipedia para fórmulas exactas
  • Factoriza el polinomio x k -c 1 x k-1 + ... + c k .
  • Las raíces del polinomio son los números necesarios a 1 , ..., a k .

Para variar k, encuentre un primo n <= q <2n usando, por ejemplo, Miller-Rabin, y realice los pasos con todos los números de módulo reducido q.

EDITAR: La versión anterior de esta respuesta indicaba que en lugar de Z q , donde q es primo, es posible usar un campo finito de la característica 2 (q = 2 ^ (log n)). Este no es el caso, ya que las fórmulas de Newton requieren división por números hasta k.

sdcvvc
fuente
66
No tiene que usar un campo principal, también puede usarlo q = 2^(log n). (¡¿Cómo hiciste los súper y subíndices ?!)
Heinrich Apfelmus
49
+1 Esto es muy, muy inteligente. Al mismo tiempo, es cuestionable si realmente vale la pena el esfuerzo o si (partes de) esta solución a un problema bastante artificial se puede reutilizar de otra manera. E incluso si se tratara de un problema del mundo real, en muchas plataformas la O(N^2)solución más trivial probablemente superará a esta belleza incluso por un nivel razonablemente alto N. Me hace pensar en esto: tinyurl.com/c8fwgw Sin embargo, ¡buen trabajo! No habría tenido la paciencia de arrastrarme a través de todas las matemáticas :)
back2dos
167
Creo que esta es una respuesta maravillosa. Creo que esto también ilustra cuán pobre de una pregunta de entrevista sería extender los números faltantes más allá de uno. Incluso el primero es una especie de gotchya, pero es bastante común que básicamente muestra "hiciste alguna preparación para la entrevista". Pero esperar que un experto en CS sepa que va más allá de k = 1 (especialmente "sobre el terreno" en una entrevista) es un poco tonto.
corsiKa
55
Esto está haciendo efectivamente la codificación Reed Solomon en la entrada.
David Ehrmann
78
Apuesto a que ingresar todos los números en una hash sete iterar sobre la 1...Nsuite usando búsquedas para determinar si faltan números, sería la ksolución más genérica, más rápida en promedio con respecto a las variaciones, más depurable, más fácil de mantener y comprensible. Por supuesto, la forma matemática es impresionante, pero en algún punto del camino debes ser ingeniero y no matemático. Especialmente cuando se trata de negocios.
v.oddou
243

Lo encontrará leyendo las dos páginas de Muthukrishnan - Algoritmos de flujo de datos: Rompecabezas 1: Encontrar números que faltan . Muestra exactamente la generalización que está buscando . Probablemente esto es lo que leyó su entrevistador y por qué planteó estas preguntas.

Ahora, si solo las personas comenzaran a eliminar las respuestas que están incluidas o reemplazadas por el tratamiento de Muthukrishnan, y hacer que este texto sea más fácil de encontrar. :)


También vea la respuesta directamente relacionada de sdcvvc , que también incluye pseudocódigo (¡hurra! No es necesario leer esas complicadas formulaciones matemáticas :)) (¡gracias, gran trabajo!).

Dimitris Andreou
fuente
Oooh ... eso es interesante. Tengo que admitir que estaba un poco confundido por las matemáticas, pero estaba solo hojeándolo. Podría dejarlo abierto para ver más tarde. :) Y +1 para que este enlace sea más fácil de encontrar. ;-)
Chris
2
El enlace de google books no funciona para mí. Aquí una mejor versión [archivo PostScript].
Heinrich Apfelmus
99
Guau. ¡No esperaba que esto fuera votado! La última vez que publiqué una referencia a la solución (Knuth's, en ese caso) en lugar de tratar de resolverlo yo mismo, en realidad fue rechazada: stackoverflow.com/questions/3060104/… El bibliotecario dentro de mí se regocija, gracias :)
Dimitris Andreou
@Apfelmus, tenga en cuenta que este es un borrador. (No te culpo, por supuesto, confundí el borrador con las cosas reales durante casi un año antes de encontrar el libro). Por cierto, si el enlace no funcionó, puede ir a books.google.com y buscar "Algoritmos de flujo de datos Muthukrishnan" (sin comillas), es el primero en aparecer.
Dimitris Andreou
2
Lea lo siguiente ya que las respuestas proporcionadas aquí son ridículas: stackoverflow.com/questions/4406110/…
174

Podemos resolver Q2 sumando tanto los números como los cuadrados de los números.

Entonces podemos reducir el problema a

k1 + k2 = x
k1^2 + k2^2 = y

Dónde xy yqué tan lejos están las sumas por debajo de los valores esperados.

Sustituir nos da:

(x-k2)^2 + k2^2 = y

Lo que luego podemos resolver para determinar nuestros números faltantes.

Luego.
fuente
77
+1; He probado la fórmula en Maple para números seleccionados y funciona. Sin embargo, todavía no podía convencerme POR QUÉ funciona.
polygenelubricants
44
@polygenelubricants: si desea probar la corrección, primero debe demostrar que siempre proporciona una solución correcta (es decir, siempre produce un par de números que, al eliminarlos del conjunto, daría como resultado que el resto del conjunto tenga la suma observada y la suma de cuadrados). A partir de ahí, demostrar la unicidad es tan simple como demostrar que solo produce uno de esos pares de números.
Anon
55
La naturaleza de las ecuaciones significa que obtendrá dos valores de k2 de esa ecuación. Sin embargo, a partir de la primera ecuación que utiliza para generar k1, puede ver que estos dos valores de k2 significarán que k1 es el otro valor, por lo que tiene dos soluciones que son los mismos números al revés. Si declarara abitivamente que k1> k2, entonces solo tendría una solución para la ecuación cuadrática y, por lo tanto, una solución general. Y claramente por la naturaleza de la pregunta, siempre existe una respuesta, por lo que siempre funciona.
Chris
3
Para una suma dada k1 + k2, hay muchos pares. Podemos escribir estos pares como K1 = a + b y K2 = ab donde a = (K1 + k2 / 2). a es único para una suma dada. La suma de los cuadrados (a + b) ** 2 + (ab) ** 2 = 2 * (a 2 + b 2). Para una suma dada K1 + K2, el término a 2 es fijo y vemos que la suma de los cuadrados será única debido al término b 2. Por lo tanto, los valores x e y son únicos para un par de enteros.
phkahler
8
Esto es asombroso @ user3281743 aquí hay un ejemplo. Deje que los números que faltan (k1 y k2) sean 4 y 6. Suma (1 -> 10) = 55 y Suma (1 ^ 2 -> 10 ^ 2) = 385. Ahora dejemos que x = 55 - (Suma (Todos los números restantes )) e y = 385 - (Suma (Cuadrados de todos los números restantes)) así x = 10 e y = 52. Sustituya como se muestra, lo que nos deja con: (10 - k2) ^ 2 + k2 ^ 2 = 52 que puede simplifica a: 2k ^ 2 - 20k + 48 = 0. Resolver la ecuación cuadrática te da 4 y 6 como respuesta.
AlexKoren
137

Como señaló @j_random_hacker, esto es bastante similar a Encontrar duplicados en O (n) tiempo y O (1) espacio , y una adaptación de mi respuesta allí también funciona aquí.

Suponiendo que la "bolsa" está representada por una matriz A[]de tamaño basada en 1 N - k, podemos resolver Qk en O(N)tiempo y O(k)espacio adicional.

Primero, extendemos nuestra matriz A[]por kelementos, de modo que ahora sea de tamaño N. Este es el O(k)espacio adicional. Luego ejecutamos el siguiente algoritmo de pseudocódigo:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

El primer bucle inicializa las kentradas adicionales de la misma manera que la primera entrada en la matriz (este es solo un valor conveniente que sabemos que ya está presente en la matriz; después de este paso, las entradas que faltaban en la matriz inicial de tamaño N-kson todavía falta en la matriz extendida).

El segundo bucle permuta la matriz extendida de modo que si el elemento xestá presente al menos una vez, una de esas entradas estará en la posición A[x].

Tenga en cuenta que aunque tiene un bucle anidado, todavía se ejecuta a O(N)tiempo: un intercambio solo ocurre si existe ital cosa A[i] != i, y cada intercambio establece al menos un elemento tal que A[i] == i, donde eso no era cierto antes. Esto significa que el número total de intercambios (y, por lo tanto, el número total de ejecuciones del whilecuerpo del bucle) es como máximo N-1.

El tercer bucle imprime los índices de la matriz ique no están ocupados por el valor i, lo que significa que ideben haberse perdido.

coste y flete
fuente
44
Me pregunto por qué tan poca gente vota esta respuesta e incluso no la marcó como una respuesta correcta. Aquí está el código en Python. Se ejecuta en tiempo O (n) y necesita espacio adicional O (k). pastebin.com/9jZqnTzV
wall-e
3
@caf esto es bastante similar a configurar los bits y contar los lugares donde el bit es 0. Y creo que al crear una matriz de enteros se ocupa más memoria.
Fox
55
"Establecer los bits y contar los lugares donde el bit es 0" requiere O (n) espacio extra, esta solución muestra cómo usar O (k) espacio extra.
caf
77
No funciona con flujos como entrada y modifica la matriz de entrada (aunque me gusta mucho y la idea es fructífera).
comco
3
@ v.oddou: No, está bien. El intercambio cambiará A[i], lo que significa que la próxima iteración no comparará los mismos dos valores que la anterior. Lo nuevo A[i]será lo mismo que el último bucle A[A[i]], pero lo nuevo A[A[i]]será un nuevo valor. Pruébalo y verás.
caf
128

Le pedí a un niño de 4 años que resolviera este problema. Ordenó los números y luego contó. Esto tiene un requerimiento de espacio de O (piso de la cocina), y funciona igual de fácil, sin embargo, faltan muchas bolas.

Coronel Panic
fuente
20
;) su hijo de 4 años debe acercarse a 5 o / y es un genio. mi hija de 4 años ni siquiera puede contar correctamente hasta 4 todavía. bueno, para ser justos, digamos que apenas integró finalmente la existencia de "4". de lo contrario hasta ahora ella siempre lo omitiría. "1,2,3,5,6,7" era su secuencia de conteo habitual. Le pedí que agregara lápices y ella lograría 1 + 2 = 3 al volver a numerar todo desde cero. Estoy realmente preocupado ...: '(meh ..
v.oddou
Enfoque simple pero efectivo.
PabTorre
66
O (piso de la cocina) jaja, pero ¿no sería eso O (n ^ 2)?
13
O (m²) supongo :)
Viktor Mellgren
1
@phuclv: la respuesta indicó que "Esto tiene un requisito de espacio de O (piso de la cocina)". Pero en cualquier caso, esta es una instancia en la que se puede lograr la clasificación en O (n) tiempo --- vea esta discusión .
Anthony Labarre el
36

No estoy seguro, si es la solución más eficiente, pero haría un bucle sobre todas las entradas y usaría un conjunto de bits para recordar qué números están configurados y luego probaría para 0 bits.

Me gustan las soluciones simples, e incluso creo que podría ser más rápido que calcular la suma, la suma de cuadrados, etc.

Chris Lercher
fuente
11
Propuse esta respuesta obvia, pero esto no es lo que el entrevistador quería. Dije explícitamente en la pregunta que esta no es la respuesta que estoy buscando. Otra respuesta obvia: ordenar primero. Ni el orden de O(N)conteo ni el de O(N log N)comparación es lo que estoy buscando, aunque ambas son soluciones muy simples.
polygenelubricants
@polygenelubricants: no puedo encontrar dónde dijiste eso en tu pregunta. Si considera que el conjunto de bits es el resultado, entonces no hay un segundo pase. La complejidad es (si consideramos que N es constante, como sugiere el entrevistador al decir que la complejidad está "definida en k no N") O (1), y si necesita construir un resultado más "limpio", usted obtenga O (k), que es lo mejor que puede obtener, porque siempre necesita O (k) para crear el resultado limpio.
Chris Lercher
"Tenga en cuenta que no estoy buscando la solución obvia basada en conjuntos (por ejemplo, usando un conjunto de bits". El segundo último párrafo de la pregunta original.
hrnt
99
@hmt: Sí, la pregunta se editó hace unos minutos. Solo estoy dando la respuesta, que esperaría de un entrevistado ... Construir artificialmente una solución subóptima (no puede vencer el tiempo O (n) + O (k), no importa lo que haga) no ' No tiene sentido para mí, excepto si no puede permitirse O (n) espacio adicional, pero la pregunta no es explícita al respecto.
Chris Lercher
3
He editado la pregunta nuevamente para aclarar más. Agradezco los comentarios / respuestas.
polygenelubricants
33

No he revisado las matemáticas, pero sospecho que computar Σ(n^2)en el mismo paso que calculamos Σ(n)proporcionaría suficiente información para obtener dos números faltantes, haz Σ(n^3)lo mismo si hay tres, y así sucesivamente.

AakashM
fuente
15

El problema con las soluciones basadas en sumas de números es que no tienen en cuenta el costo de almacenar y trabajar con números con grandes exponentes ... en la práctica, para que funcione para n muy grande, se usaría una biblioteca de grandes números . Podemos analizar la utilización del espacio para estos algoritmos.

Podemos analizar la complejidad de tiempo y espacio de los algoritmos de sdcvvc y Dimitris Andreou.

Almacenamiento:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

Entonces l_j \in \Theta(j log n)

Almacenamiento total utilizado: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Espacio utilizado: suponiendo que la informática a^jlleva ceil(log_2 j)tiempo, tiempo total:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

Tiempo total utilizado: \Theta(kn log n)

Si este tiempo y espacio son satisfactorios, puede usar un algoritmo recursivo simple. Sea b! I la entrada i-ésima en la bolsa, n el número de números antes de los retiros, yk el número de retiros. En la sintaxis de Haskell ...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

Almacenamiento utilizado: O(k)para lista, O(log(n))para pila: O(k + log(n)) este algoritmo es más intuitivo, tiene la misma complejidad de tiempo y usa menos espacio.

a1kmm
fuente
1
+1, se ve bien, pero me perdiste al pasar de la línea 4 a la línea 5 en el fragmento # 1, ¿podrías explicarlo más? ¡Gracias!
j_random_hacker
isInRangees O (log n) , no O (1) : compara números en el rango 1..n, por lo que tiene que comparar los bits O (log n) . No sé en qué medida este error afecta el resto del análisis.
jcsahnwaldt dice GoFundMonica
14

Espera un minuto. Como se plantea la pregunta, hay 100 números en la bolsa. No importa cuán grande sea k, el problema puede resolverse en tiempo constante porque puede usar un conjunto y eliminar números del conjunto en un máximo de 100 k iteraciones de un bucle. 100 es constante. El conjunto de números restantes es su respuesta.

Si generalizamos la solución a los números del 1 al N, nada cambia excepto que N no es una constante, por lo que estamos en el tiempo O (N - k) = O (N). Por ejemplo, si usamos un conjunto de bits, establecemos los bits a 1 en tiempo O (N), iteramos a través de los números, configuramos los bits a 0 a medida que avanzamos (O (Nk) = O (N)) y luego tener la respuesta

Me parece que el entrevistador le estaba preguntando cómo imprimir el contenido del conjunto final en tiempo O (k) en lugar de tiempo O (N). Claramente, con un conjunto de bits, debe iterar a través de todos los N bits para determinar si debe imprimir el número o no. Sin embargo, si cambia la forma en que se implementa el conjunto, puede imprimir los números en k iteraciones. Esto se hace colocando los números en un objeto que se almacenará tanto en un conjunto de hash como en una lista doblemente vinculada. Cuando elimina un objeto del conjunto de hash, también lo elimina de la lista. Las respuestas se dejarán en la lista que ahora tiene una longitud k.

JeremyP
fuente
99
¡Esta respuesta es demasiado simple, y todos sabemos que las respuestas simples no funcionan! ;) En serio, la pregunta original probablemente debería enfatizar el requisito de espacio O (k).
DK.
El problema no es que sea simple, sino que tendrá que usar O (n) memoria adicional para el mapa. El problema me resolvió en tiempo constante y memoria constante
Mojo Risin
3
Apuesto a que puedes probar que la solución mínima es al menos O (N). porque menos significaría que ni siquiera MIRAS algunos números, y dado que no hay pedidos especificados, mirar TODOS los números es obligatorio.
v.oddou
Si consideramos la entrada como una secuencia, yn es demasiado grande para guardarla en la memoria, el requisito de memoria O (k) tiene sentido. Sin embargo, todavía podemos usar hashing: solo haga k ^ 2 cubos y use el algoritmo de suma simple en cada uno de ellos. Eso es solo k ^ 2 de memoria y se pueden usar algunos cubos más para obtener una alta probabilidad de éxito.
Thomas Ahle
8

Para resolver la pregunta de 2 (y 3) números faltantes, puede modificar quickselect, que en promedio se ejecuta O(n)y usa memoria constante si la partición se realiza en el lugar.

  1. Particione el conjunto con respecto a un pivote aleatorio pen particiones l, que contienen números más pequeños que el pivote, y rque contienen números mayores que el pivote.

  2. Determine en qué particiones están los 2 números faltantes comparando el valor de pivote con el tamaño de cada partición ( p - 1 - count(l) = count of missing numbers in ly n - count(r) - p = count of missing numbers in r)

  3. a) Si a cada partición le falta un número, utilice el enfoque de la diferencia de sumas para encontrar cada número faltante.

    (1 + 2 + ... + (p-1)) - sum(l) = missing #1 y ((p+1) + (p+2) ... + n) - sum(r) = missing #2

    b) Si a una partición le faltan ambos números y la partición está vacía, entonces los números que faltan son (p-1,p-2)o (p+1,p+2) dependen de qué partición faltan los números.

    Si a una partición le faltan 2 números pero no está vacía, vuelva a esa partición.

Con solo 2 números faltantes, este algoritmo siempre descarta al menos una partición, por lo que conserva la O(n)complejidad de tiempo promedio de la selección rápida. De manera similar, con 3 números faltantes, este algoritmo también descarta al menos una partición con cada pasada (porque como con 2 números faltantes, como máximo solo 1 partición contendrá múltiples números faltantes). Sin embargo, no estoy seguro de cuánto disminuye el rendimiento cuando se agregan más números faltantes.

Aquí hay una implementación que no usa particionamiento en el lugar, por lo que este ejemplo no cumple con los requisitos de espacio, pero ilustra los pasos del algoritmo:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Manifestación

FuzzyTree
fuente
Particionar el conjunto es como usar un espacio lineal. Al menos no funcionaría en una configuración de transmisión.
Thomas Ahle
@ThomasAhle ver en.wikipedia.org/wiki/Selection_algorithm#Space_complexity . dividir el conjunto en su lugar solo requiere O (1) espacio adicional, no espacio lineal. En una configuración de transmisión sería O (k) espacio adicional, sin embargo, la pregunta original no menciona la transmisión.
FuzzyTree
No directamente, pero escribe "debe escanear la entrada en O (N), pero solo puede capturar una pequeña cantidad de información (definida en términos de k no N)", que generalmente es la definición de transmisión. Mover todos los números para la partición no es realmente posible a menos que tenga una matriz de tamaño N. Es solo que la pregunta tiene muchas respuestas que parecen ignorar esta restricción.
Thomas Ahle
1
Pero como usted dice, ¿el rendimiento puede disminuir a medida que se agregan más números? También podemos usar el algoritmo de mediana de tiempo lineal, para obtener siempre un corte perfecto, pero si los números k están bien distribuidos en 1, ..., n, no tendrá que pasar por niveles de "profundidad" antes de podar. alguna rama?
Thomas Ahle
2
El peor tiempo de ejecución es de hecho nlogk porque necesita procesar toda la entrada en la mayoría de los tiempos de logk, y luego es una secuencia geométrica (una que comienza con a lo sumo n elementos). Los requisitos de espacio se registran cuando se implementan con una recursión simple, pero se pueden hacer O (1) ejecutando una selección rápida real y asegurando la longitud correcta de cada partición.
emu
7

Aquí hay una solución que utiliza k bits de almacenamiento adicional, sin ningún truco inteligente y sencillo. Tiempo de ejecución O (n), espacio extra O (k). Solo para demostrar que esto se puede resolver sin leer primero la solución o ser un genio:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}
gnasher729
fuente
¿Usted quiere (data [n - 1 - odd] % 2 == 1) ++odd;?
Charles
2
¿Podría explicar cómo funciona esto? No entiendo.
Teepeemm
La solución sería muy, muy simple si pudiera usar una matriz de (n + k) booleanos para el almacenamiento temporal, pero eso no está permitido. Así que reorganizo los datos, colocando los números pares al principio y los impares al final de la matriz. ¡Ahora los bits más bajos de esos n números se pueden usar para almacenamiento temporal, porque sé cuántos números pares e impares hay y puedo reconstruir los bits más bajos! Estos n bits y los k bits adicionales son exactamente los (n + k) booleanos que necesitaba.
gnasher729
2
Esto no funcionaría si los datos fueran demasiado grandes para guardarlos en la memoria, y solo los vieras como una secuencia. Aunque deliciosamente hacky :)
Thomas Ahle
La complejidad del espacio puede ser O (1). En una primera pasada, procesa todos los números <(n - k) exactamente por este algoritmo, sin usar 'extra'. En una segunda pasada, borra nuevamente los bits de paridad y usa las primeras k posiciones para indexar números (nk) ... (n).
emu
5

¿Puedes verificar si cada número existe? En caso afirmativo, puede intentar esto:

S = suma de todos los números en la bolsa (S <5050)
Z = suma de los números que faltan 5050 - S

si los números que faltan son xy yluego:

x = Z - y y
max (x) = Z - 1

Entonces verifica el rango de 1a max(x)y encuentra el número

Ilian Iliev
fuente
1
¿Qué max(x)significa cuándo xes un número?
Thomas Ahle
2
probablemente quiere decir máximo del conjunto de los números
JavaHopper
si tenemos más de 2 números, esta solución se
rompería
4

Puede ser que este algoritmo funcione para la pregunta 1:

  1. Precomputar xor de los primeros 100 enteros (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
  2. xor los elementos a medida que siguen viniendo de la secuencia de entrada (val1 = val1 ^ next_input)
  3. respuesta final = val ^ val1

O mejor:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

De hecho, este algoritmo puede expandirse para dos números faltantes. El primer paso sigue siendo el mismo. Cuando llamamos a GetValue con dos números faltantes, el resultado será a a1^a2son los dos números faltantes. Digamos

val = a1^a2

Ahora para tamizar a1 y a2 de val tomamos cualquier bit establecido en val. Digamos que el ithbit se establece en val. Eso significa que a1 y a2 tienen paridad diferente en la ithposición de bit. Ahora hacemos otra iteración en la matriz original y mantenemos dos valores xor. Uno para los números que tienen el conjunto de bits i-ésimo y otro que no tiene el conjunto de bits i-ésimo. Ahora tenemos dos cubos de números, y está garantizado que a1 and a2estarán en cubos diferentes. Ahora repita lo mismo que hicimos para encontrar un elemento faltante en cada uno de los cubos.

bashrc
fuente
Esto solo resuelve el problema k=1, ¿verdad? Pero me gusta usar xormás de sumas, parece un poco más rápido.
Thomas Ahle
@ThomasAhle Sí. Lo he llamado en mi respuesta.
bashrc
Derecha. ¿Tiene idea de lo que podría ser un xor de "segundo orden", para k = 2? Similar al uso de cuadrados para la suma, ¿podríamos "cuadrado" para xor?
Thomas Ahle
1
@ThomasAhle Lo modificó para que funcione con 2 números faltantes.
bashrc
esta es mi forma favorita :)
robert king
3

Puede resolver Q2 si tiene la suma de ambas listas y el producto de ambas listas.

(l1 es el original, l2 es la lista modificada)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

Podemos optimizar esto ya que la suma de una serie aritmética es n veces el promedio del primer y último término:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

Ahora sabemos que (si a y b son los números eliminados):

a + b = d
a * b = m

Entonces podemos reorganizar a:

a = s - b
b * (s - b) = m

Y multiplicar:

-b^2 + s*b = m

Y reorganizar para que el lado derecho sea cero:

-b^2 + s*b - m = 0

Entonces podemos resolver con la fórmula cuadrática:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Código de muestra de Python 3:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

No conozco la complejidad de las funciones sqrt, reduce y sum, por lo que no puedo resolver la complejidad de esta solución (si alguien lo sabe, comente a continuación).

Tuomas Laakkonen
fuente
¿Cuánto tiempo y memoria usa para calcular x1*x2*x3*...?
Thomas Ahle
@ThomasAhle Es O (n) -time y O (1) -space en la longitud de la lista, pero en realidad es más que la multiplicación (al menos en Python) es O (n ^ 1.6) -time en la longitud de el número y los números son O (log n) -space en su longitud.
Tuomas Laakkonen
@ThomasAhle No, log (a ^ n) = n * log (a) para que tenga espacio O (l log k) para almacenar el número. Entonces, dada una lista de longitud l y números originales de longitud k, tendrías un espacio O (l) pero el factor constante (log k) sería menor que simplemente escribirlos todos. (No creo que mi método sea una forma particularmente buena de responder la pregunta).
Tuomas Laakkonen
3

Para Q2, esta es una solución que es un poco más ineficiente que las otras, pero que todavía tiene tiempo de ejecución O (N) y ocupa espacio O (k).

La idea es ejecutar el algoritmo original dos veces. En el primero obtienes un número total que falta, que te da un límite superior de los números que faltan. Llamemos a este número N. Usted sabe que los dos números que faltan van a sumar N, por lo que el primer número solo puede estar en el intervalo [1, floor((N-1)/2)]mientras que el segundo va a estar dentro [floor(N/2)+1,N-1].

Por lo tanto, realiza un bucle en todos los números una vez más, descartando todos los números que no están incluidos en el primer intervalo. Los que son, lleva un registro de su suma. Finalmente, conocerá uno de los dos números que faltan y, por extensión, el segundo.

Tengo la sensación de que este método podría generalizarse y tal vez se ejecuten múltiples búsquedas en "paralelo" durante una sola pasada sobre la entrada, pero aún no he descubierto cómo.

Svalorzen
fuente
Jajaja, sí, esta es la misma solución que se me ocurrió para Q2, solo calculando la suma nuevamente tomando los negativos para todos los números por debajo de N / 2, ¡pero esto es aún mejor!
xjcl
2

Creo que esto se puede hacer sin ecuaciones y teorías matemáticas complejas. A continuación se muestra una propuesta para una solución de complejidad de tiempo in situ y O (2n):

Supuestos del formulario de entrada:

# de números en la bolsa = n

# de números faltantes = k

Los números en la bolsa están representados por una matriz de longitud n

Longitud de la matriz de entrada para algo = n

Las entradas que faltan en la matriz (números extraídos de la bolsa) se reemplazan por el valor del primer elemento de la matriz.

P.ej. Inicialmente, la bolsa se ve como [2,9,3,7,8,6,4,5,1,10]. Si se saca 4, el valor de 4 se convertirá en 2 (el primer elemento de la matriz). Por lo tanto, después de sacar 4, la bolsa se verá como [2,9,3,7,8,6,2,5,1,10]

La clave de esta solución es etiquetar el ÍNDICE de un número visitado negando el valor en ese ÍNDICE a medida que se recorre la matriz.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }
cazador
fuente
Esto usa demasiada memoria.
Thomas Ahle
2

Hay una forma general de generalizar algoritmos de transmisión como este. La idea es utilizar un poco de aleatorización para, con suerte, 'difundir' los kelementos en subproblemas independientes, donde nuestro algoritmo original nos resuelve el problema. Esta técnica se utiliza en la reconstrucción de señales dispersas, entre otras cosas.

  • Haga una matriz a, de tamaño u = k^2.
  • Escoja cualquier función hash universales , h : {1,...,n} -> {1,...,u}. (Al igual que el turno múltiple )
  • Para cada uno ien 1, ..., naumentoa[h(i)] += i
  • Para cada número xen la secuencia de entrada, decremente a[h(x)] -= x.

Si todos los números faltantes se han dividido en segmentos diferentes, los elementos distintos de cero de la matriz ahora contendrán los números faltantes.

La probabilidad de que un par particular se envíe al mismo depósito es menor que 1/upor definición de una función hash universal. Como hay aproximadamente k^2/2pares, tenemos que la probabilidad de error es como máximo k^2/2/u=1/2. Es decir, tenemos éxito con una probabilidad de al menos 50%, y si uaumentamos aumentamos nuestras posibilidades.

Tenga en cuenta que este algoritmo ocupa k^2 lognbits de espacio (necesitamos lognbits por segmento de matriz). Esto coincide con el espacio requerido por la respuesta de @Dimitris Andreou (en particular, el requisito de espacio de factorización polinómica, que también es aleatorio). Este algoritmo también tiene constante tiempo por actualización, en lugar de tiempo ken el caso de sumas de potencia.

De hecho, podemos ser aún más eficientes que el método de la suma de potencia utilizando el truco descrito en los comentarios.

Thomas Ahle
fuente
Nota: También podemos usar xoren cada cubo, en lugar de hacerlo sum, si eso es más rápido en nuestra máquina.
Thomas Ahle
Interesante, pero creo que esto sólo respeta el espacio de restricción cuando k <= sqrt(n)- al menos si u=k^2? Supongamos que k = 11 yn = 100, entonces tendría 121 cubos y el algoritmo terminaría siendo similar a tener una matriz de 100 bits que marca a medida que lee cada # de la secuencia. Aumentar umejora las posibilidades de éxito, pero hay un límite para cuánto puede aumentarlo antes de exceder la restricción de espacio.
FuzzyTree
1
El problema tiene más sentido para nmucho más grande que k, creo, pero en realidad se puede reducir el espacio k logncon un método muy similar al hashing descrito, sin dejar de tener actualizaciones de tiempo constantes. Se describe en gnunet.org/eppstein-set-reconciliation , como el método de la suma de poderes, pero básicamente hash a 'dos ​​de k' buckets con una función hash fuerte como hashing de tabulación, lo que garantiza que algún bucket tendrá solo un elemento . Para decodificar, identifica ese depósito y elimina el elemento de sus dos depósitos, lo que (probablemente) libera otro depósito, etc.
Thomas Ahle
2

Una solución muy simple para Q2 que me sorprende que nadie haya respondido ya. Usa el método de Q1 para encontrar la suma de los dos números que faltan. Denotémoslo por S, entonces uno de los números que faltan es menor que S / 2 y el otro es mayor que S / 2 (duh). Suma todos los números del 1 al S / 2 y compáralo con el resultado de la fórmula (de manera similar al método en Q1) para encontrar el menor entre los números que faltan. Restarlo de S para encontrar el número que falta más grande.

Gilad Deutsch
fuente
Creo que esto es lo mismo que la respuesta de Svalorzen , pero usted lo explicó con mejores palabras. ¿Tienes alguna idea de cómo generalizarlo a Qk?
John McClane
Perdón por perder la otra respuesta. No estoy seguro de si es posible generalizarlo a $ Q_k $ ya que en ese caso no puede vincular el elemento más pequeño que falta a algún rango. Usted sabe que algún elemento debe ser menor que $ S / k $, pero eso podría ser cierto para varios elementos
Gilad Deutsch
1

Muy buen problema. Me gustaría usar una diferencia establecida para Qk. Muchos lenguajes de programación incluso lo admiten, como en Ruby:

missing = (1..100).to_a - bag

Probablemente no sea la solución más eficiente, pero es una que usaría en la vida real si me enfrentara a tal tarea en este caso (límites conocidos, límites bajos). Si el conjunto de números fuera muy grande, consideraría un algoritmo más eficiente, por supuesto, pero hasta entonces la solución simple sería suficiente para mí.

Polvo oscuro
fuente
1
Esto usa demasiado espacio.
Thomas Ahle
@ThomasAhle: ¿Por qué agrega comentarios inútiles a cada segunda respuesta? ¿Qué quieres decir con que está usando demasiado espacio?
DarkDust
Porque la pregunta dice que "No podemos permitirnos ningún espacio adicional proporcional a N." Esta solución hace exactamente eso.
Thomas Ahle
1

Puedes intentar usar un filtro Bloom . Inserta cada número en la bolsa en la flor, luego itera sobre el conjunto completo de 1-k hasta informar cada uno que no se encuentre. Es posible que esto no encuentre la respuesta en todos los escenarios, pero podría ser una solución lo suficientemente buena.

jdizzle
fuente
También está el filtro de recuento de floración, que permite la eliminación. Luego, puede agregar todos los números y eliminar los que ve en la transmisión.
Thomas Ahle
Jaja, esta es probablemente una de las respuestas más prácticas, pero recibe poca atención.
ldog
1

Tomaría un enfoque diferente a esa pregunta e investigaría al entrevistador para obtener más detalles sobre el gran problema que está tratando de resolver. Dependiendo del problema y los requisitos que lo rodean, la solución obvia basada en conjuntos podría ser lo correcto y el enfoque de generar una lista y elegirlo después podría no serlo.

Por ejemplo, puede ser que el entrevistador envíe nmensajes y necesite saber kque eso no resultó en una respuesta y necesita saberlo en el menor tiempo posible del reloj de pared después de que n-kllegue la respuesta. Supongamos también que la naturaleza del canal de mensajes es tal que incluso cuando se ejecuta a toda potencia, hay suficiente tiempo para procesar algo entre mensajes sin tener ningún impacto en cuánto tiempo se tarda en producir el resultado final después de que llega la última respuesta. Se puede aprovechar ese tiempo insertando una faceta de identificación de cada mensaje enviado en un conjunto y eliminándolo a medida que llegue cada respuesta correspondiente. Una vez que llega la última respuesta, lo único que se debe hacer es eliminar su identificador del conjunto, que en implementaciones típicas tomaO(log k+1). Después de eso, el conjunto contiene la lista de kelementos que faltan y no hay procesamiento adicional para hacer.

Ciertamente, este no es el enfoque más rápido para el procesamiento por lotes de bolsas pregeneradas de números porque todo funciona O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). Pero funciona para cualquier valor de k(incluso si no se conoce con anticipación) y en el ejemplo anterior se aplicó de una manera que minimiza el intervalo más crítico.

Blrfl
fuente
¿Funcionaría si solo tuviera O (k ^ 2) memoria adicional?
Thomas Ahle
1

Puede motivar la solución al pensar en términos de simetrías (grupos, en lenguaje matemático). No importa el orden del conjunto de números, la respuesta debe ser la misma. Si va a utilizar kfunciones para ayudar a determinar los elementos que faltan, debe pensar qué funciones tienen esa propiedad: simétrica. La función s_1(x) = x_1 + x_2 + ... + x_nes un ejemplo de una función simétrica, pero hay otras de mayor grado. En particular, considere las funciones simétricas elementales . La función simétrica elemental del grado 2 es s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_nla suma de todos los productos de dos elementos. Del mismo modo para las funciones simétricas elementales de grado 3 y superior. Obviamente son simétricos. Además, resulta que son los bloques de construcción para todas las funciones simétricas.

Puede construir las funciones simétricas elementales a medida que avanza al notar eso s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Pensar más sobre esto debería convencerlo de que s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))así sucesivamente, para que puedan calcularse de una sola vez.

¿Cómo sabemos qué elementos faltaban en la matriz? Piensa en el polinomio (z-x_1)(z-x_2)...(z-x_n). Se evalúa 0si pones alguno de los números x_i. Expandiendo el polinomio, obtienes z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. Aquí también aparecen las funciones simétricas elementales, lo cual no es una sorpresa, ya que el polinomio debería permanecer igual si aplicamos alguna permutación a las raíces.

Entonces podemos construir el polinomio e intentar factorizarlo para descubrir qué números no están en el conjunto, como otros han mencionado.

Finalmente, si estamos preocupados por el desbordamiento de memoria con números grandes (el enésimo polinomio simétrico será del orden 100!), podemos hacer estos cálculos mod pdonde pes un primo mayor que 100. En ese caso, evaluamos el polinomio mod py descubrimos que nuevamente evalúa a 0cuando la entrada es un número en el conjunto, y se evalúa a un valor distinto de cero cuando la entrada es un número que no está en el conjunto. Sin embargo, como otros han señalado, para obtener los valores del polinomio en el tiempo que depende k, no N, tenemos que factorizar el polinomio mod p.

Edward Doolittle
fuente
1

Sin embargo, otra forma es usar el filtrado gráfico residual.

Supongamos que tenemos los números 1 a 4 y falta 3. La representación binaria es la siguiente,

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

Y puedo crear un diagrama de flujo como el siguiente.

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

Tenga en cuenta que el gráfico de flujo contiene x nodos, mientras que x es el número de bits. Y el número máximo de aristas es (2 * x) -2.

Entonces, para un entero de 32 bits, ocupará O (32) espacio u O (1) espacio.

Ahora, si elimino la capacidad de cada número a partir de 1,2,4, me queda un gráfico residual.

0 ----------> 1 ---------> 1

Finalmente ejecutaré un bucle como el siguiente,

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

Ahora el resultado está en resultcontiene números que no faltan también (falso positivo). Pero la k <= (tamaño del resultado) <= n cuando kfaltan elementos.

Revisaré la lista dada por última vez para marcar el resultado como perdido o no.

Entonces la complejidad del tiempo será O (n).

Finalmente, es posible reducir el número de falsos positivos (y el espacio necesario) mediante la adopción de nodos 00, 01, 11, 10en lugar de sólo 0y 1.

shuva
fuente
No entiendo tu diagrama gráfico. ¿Qué representan los nodos, aristas y números? ¿Por qué se dirigen algunos de los bordes y no otros?
desde el
De hecho, realmente no entiendo tu respuesta, ¿puedes aclarar un poco más?
desde el
1

Probablemente necesite aclaraciones sobre lo que significa O (k).

Aquí hay una solución trivial para k arbitraria: para cada v en su conjunto de números, acumule la suma de 2 ^ v. Al final, repita i de 1 a N. Si la suma AND con 2 bits i es cero, entonces me falta. (O numéricamente, si el piso de la suma dividido por 2 ^ i es par. Or sum modulo 2^(i+1)) < 2^i.)

Fácil, verdad? O (N) tiempo, O (1) almacenamiento, y admite k arbitrario.

Excepto que estás calculando números enormes que en una computadora real requerirían espacio O (N). De hecho, esta solución es idéntica a un vector de bits.

Entonces podría ser inteligente y calcular la suma y la suma de los cuadrados y la suma de los cubos ... hasta la suma de v ^ k, y hacer las matemáticas elegantes para extraer el resultado. Pero esos también son números grandes, lo que plantea la pregunta: ¿de qué modelo abstracto de operación estamos hablando? ¿Cuánto cabe en el espacio O (1) y cuánto tiempo lleva sumar números del tamaño que necesite?

sfink
fuente
¡Buena respuesta! Una pequeña cosa: "Si sum modulo 2 ^ i es cero, entonces me falta" es incorrecto. Pero está claro lo que se pretende. Creo que "si el módulo de suma 2 ^ (i + 1) es menor que 2 ^ i, entonces me falta" sería correcto. (Por supuesto, en la mayoría de los lenguajes de programación
usaríamos el
1
Gracias, tienes toda la razón! Solucionado, aunque era flojo y me desvié de la notación matemática ... oh, y eso también lo arruiné. Arreglando de nuevo ...
sfink
1

Aquí hay una solución que no se basa en matemáticas complejas como lo hacen las respuestas de sdcvvc / Dimitris Andreou, no cambia la matriz de entrada como lo hicieron caf y Coronel Panic, y no usa el bitset de enorme tamaño como Chris Lercher, JeremyP y muchos otros lo hicieron. Básicamente, comencé con la idea de Svalorzen / Gilad Deutch para Q2, la generalicé al caso común Qk y la implementé en Java para demostrar que el algoritmo funciona.

La idea

Supongamos que tenemos un intervalo arbitrario I del cual solo sabemos que contiene al menos uno de los números que faltan. Después de una pasada a través de la matriz de entrada, mirando sólo los números de I , podemos obtener tanto la suma S y la cantidad Q de los números que falta de I . Hacemos esto simplemente disminuyendo la longitud de I cada vez que encontramos un número de I (para obtener Q ) y disminuyendo la suma calculada previamente de todos los números en I por ese número encontrado cada vez (para obtener S ).

Ahora nos centraremos en S y Q . Si Q = 1 , significa que entonces me contiene sólo uno de los números que faltan, y este número es claramente S . Marcamos I como terminado (se llama "inequívoco" en el programa) y lo dejamos fuera de consideración. Por otro lado, si Q> 1 , se puede calcular el promedio A = S / Q de los números que faltan contenida en I . Como todos los números son distintos, al menos uno de dichos números es estrictamente menor que A y al menos una es estrictamente mayor que A . Ahora nos separamos yo en unaen dos intervalos más pequeños, cada uno de los cuales contiene al menos un número faltante. Tenga en cuenta que no importa a cuál de los intervalos asignamos A en caso de que sea un número entero.

Realizamos el siguiente paso de matriz calculando S y Q para cada uno de los intervalos por separado (pero en el mismo paso) y luego marcamos los intervalos con Q = 1 y los intervalos divididos con Q> 1 . Continuamos este proceso hasta que no haya nuevos intervalos "ambiguos", es decir, no tenemos nada que dividir porque cada intervalo contiene exactamente un número faltante (y siempre sabemos este número porque sabemos S ). Comenzamos desde el único intervalo de "rango completo" que contiene todos los números posibles (como [1..N] en la pregunta).

Análisis de complejidad de tiempo y espacio.

El número total de pases p que necesitamos hacer hasta que el proceso se detenga nunca es mayor que los números faltantes cuentan k . La desigualdad p <= k puede demostrarse rigurosamente. Por otro lado, también hay un límite superior empírico p <log 2 N + 3 que es útil para valores grandes de k . Necesitamos hacer una búsqueda binaria para cada número de la matriz de entrada para determinar el intervalo al que pertenece. Esto agrega el multiplicador log k a la complejidad del tiempo.

En total, la complejidad del tiempo es O (N ᛫ min (k, log N) ᛫ log k) . Tenga en cuenta que para k grande , esto es significativamente mejor que el del método sdcvvc / Dimitris Andreou, que es O (N ᛫ k) .

Para su trabajo, el algoritmo requiere O (k) de espacio adicional para almacenar en la mayoría de los intervalos de k , que es significativamente mejor que O (N) en soluciones de "conjunto de bits".

Implementación de Java

Aquí hay una clase de Java que implementa el algoritmo anterior. Siempre devuelve una matriz ordenada de números faltantes. Además de eso, no requiere que los números que faltan cuenten k porque lo calcula en la primera pasada. El rango completo de números viene dado por los parámetros minNumbery maxNumber(por ejemplo, 1 y 100 para el primer ejemplo en la pregunta).

public class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;

        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }

        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }

    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}

Para ser justos, esta clase recibe información en forma de NumberBagobjetos. NumberBagno permite la modificación de la matriz y el acceso aleatorio y también cuenta cuántas veces se solicitó la matriz para el recorrido secuencial. También es más adecuado para pruebas de matriz grande que Iterable<Integer>porque evita el encajonamiento de intvalores primitivos y permite envolver una parte de una gran int[]para una preparación de prueba conveniente. No es difícil de reemplazar, en caso dado, NumberBagpor int[]o Iterable<Integer>escribir en la findfirma, mediante el cambio de dos bucles en que foreach en otros más.

import java.util.*;

public abstract class NumberBag {
    private int passCount;

    public void startOver() {
        passCount++;
    }

    public final int getPassCount() {
        return passCount;
    }

    public abstract boolean hasNext();

    public abstract int next();

    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;

            public void startOver() {
                super.startOver();
                index = fromIndex;
            }

            public boolean hasNext() {
                return index < toIndex;
            }

            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }

    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }

    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;

            public void startOver() {
                super.startOver();
                it = base.iterator();
            }

            public boolean hasNext() {
                return it.hasNext();
            }

            public int next() {
                return it.next();
            }
        };
    }
}

Pruebas

A continuación se dan ejemplos simples que demuestran el uso de estas clases.

import java.util.*;

public class SimpleTest {
    public static void main(String[] args) {
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());

        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
                inputList, Arrays.toString(output), bag.getPassCount());

        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
    }
}

Las pruebas de matriz grande se pueden realizar de esta manera:

import java.util.*;

public class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;

    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }

    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }

    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }

    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }

    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }

    public static void main(String[] args) {
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 20_000);
        strideCheck(100_000, 2, 99_998, 1_282, 15);
        MIN_NUMBER = -2_000_000_000;
        strideCheck(300_000_000, 1, 10, 1, 1);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
    }
}

Pruébalos en Ideone

John McClane
fuente
0

Creo que tengo un algoritmo de O(k)tiempo y O(log(k))espacio, dado que tiene las funciones floor(x)y log2(x)para enteros arbitrariamente grandes disponibles:

Tiene un kentero largo de un bit (de ahí el log8(k)espacio) donde agrega el x^2, donde x es el siguiente número que encuentra en la bolsa: s=1^2+2^2+...esto lleva O(N)tiempo (lo cual no es un problema para el entrevistador). Al final obtienes j=floor(log2(s))cuál es el número más grande que estás buscando. Entonces s=s-jy haces de nuevo lo anterior:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Ahora, por lo general, no tiene las funciones floor y log2 para los 2756enteros -bit, sino para los dobles. ¿Entonces? Simplemente, por cada 2 bytes (o 1, o 3, o 4) puede usar estas funciones para obtener los números deseados, pero esto agrega un O(N)factor a la complejidad del tiempo

CostasGR43
fuente
0

Esto puede sonar estúpido, pero, en el primer problema que se le presenta, tendría que ver todos los números restantes en la bolsa para sumarlos y encontrar el número que falta usando esa ecuación.

Entonces, como puede ver todos los números, solo busque el número que falta. Lo mismo ocurre cuando faltan dos números. Bastante simple, creo. No tiene sentido usar una ecuación cuando puedes ver los números restantes en la bolsa.

Stephan M
fuente
2
Creo que el beneficio de resumirlos es que no tienes que recordar qué números ya has visto (por ejemplo, no hay un requisito de memoria adicional). De lo contrario, la única opción es retener un conjunto de todos los valores vistos y luego iterar sobre ese conjunto nuevamente para encontrar el que falta.
Dan Tao
3
Esta pregunta generalmente se hace con la estipulación de la complejidad del espacio O (1).
La suma de los primeros N números es N (N + 1) / 2. Para N = 100, Suma = 100 * (101) / 2 = 5050;
tmarthal
0

Creo que esto se puede generalizar así:

Denote S, M como los valores iniciales para la suma de series aritméticas y multiplicación.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

Debería pensar en una fórmula para calcular esto, pero ese no es el punto. De todos modos, si falta un número, ya proporcionó la solución. Sin embargo, si faltan dos números, denotemos la nueva suma y el múltiplo total por S1 y M1, que serán los siguientes:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

Como conoce S1, M1, M y S, la ecuación anterior se puede resolver para encontrar ayb, los números que faltan.

Ahora para los tres números que faltan:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

Ahora su incógnita es 3, mientras que solo tiene dos ecuaciones que puede resolver.

Un mil usos
fuente
Sin embargo, la multiplicación se vuelve bastante grande. Además, ¿cómo generalizas a más de 2 números faltantes?
Thomas Ahle
He intentado estas fórmulas en una secuencia muy simple con N = 3 y números faltantes = {1, 2}. No funcioné, ya que creo que el error está en las fórmulas (2) que deberían leer M1 = M / (a * b)(vea esa respuesta ). Entonces funciona bien.
dma_k
0

No sé si esto es eficiente o no, pero me gustaría sugerir esta solución.

  1. Calcular xor de los 100 elementos
  2. Calcule xor de los 98 elementos (después de eliminar los 2 elementos)
  3. Ahora (resultado de 1) XOR (resultado de 2) le da el xor de los dos números faltantes, es decir, XOR b si a y b son los elementos faltantes
    4. Obtenga la suma de los números faltantes con su enfoque habitual de suma la fórmula diff y digamos que la diferencia es d.

Ahora ejecute un bucle para obtener los posibles pares (p, q) que se encuentran en [1, 100] y suman d.

Cuando se obtiene un par, verifique si (resultado de 3) XOR p = q y si es así, hemos terminado.

Corríjame si estoy equivocado y también comente sobre la complejidad del tiempo si esto es correcto

usuario2221214
fuente
2
No creo que la suma y xor definan de manera única dos números. Ejecutar un ciclo para obtener todas las k-tuplas posibles que suman d toma tiempo O (C (n, k-1)) = O (n <sup> k-1 </sup>), que, para k> 2, es malo.
Teepeemm
0

Podemos hacer Q1 y Q2 en O (log n) la mayor parte del tiempo.

Supongamos que nuestro memory chipconsiste en una matriz de nnúmero de test tubes. Y un número xen el tubo de ensayo está representado por x milliliterquímico-líquido.

Supongamos que nuestro procesador es a laser light. Cuando encendemos el láser, atraviesa todos los tubos perpendicularmente a su longitud. Cada vez que pasa a través del líquido químico, la luminosidad se reduce en 1. Y pasar la luz a cierta marca de mililitros es una operación de O(1).

Ahora, si encendemos nuestro láser en el centro del tubo de ensayo y obtenemos la salida de luminosidad

  • es igual a un valor precalculado (calculado cuando no faltan números), entonces los números que faltan son mayores que n/2.
  • Si nuestra salida es menor, entonces hay al menos un número faltante que es menor que n/2. También podemos verificar si la luminosidad se reduce en 1o 2. si se reduce para 1entonces, un número faltante es menor que n/2y otro es mayor que n/2. Si se reduce para 2entonces, ambos números son más pequeños que n/2.

Podemos repetir el proceso anterior una y otra vez reduciendo nuestro dominio del problema. En cada paso, reducimos el dominio a la mitad. Y finalmente podemos llegar a nuestro resultado.

Algoritmos paralelos que vale la pena mencionar (porque son interesantes),

  • ordenar por algún algoritmo paralelo, por ejemplo, la fusión paralela se puede hacer a O(log^3 n)tiempo. Y luego el número faltante se puede encontrar por búsqueda binaria en el O(log n)tiempo.
  • Teóricamente, si tenemos nprocesadores, cada proceso puede verificar una de las entradas y establecer un indicador que identifique el número (convenientemente en una matriz). Y en el siguiente paso, cada proceso puede verificar cada indicador y finalmente generar el número que no está marcado. Todo el proceso llevará O(1)tiempo. Tiene O(n)espacio adicional / requisito de memoria.

Tenga en cuenta que los dos algoritmos paralelos proporcionados anteriormente pueden necesitar espacio adicional como se menciona en el comentario .

shuva
fuente
Si bien el método del tubo de ensayo con láser es realmente interesante, espero que esté de acuerdo en que no se traduce bien en instrucciones de hardware y, por lo tanto, es muy poco probable que esté O(logn)en una computadora.
SirGuy
1
En cuanto a su método de clasificación, eso requerirá una cantidad de espacio adicional que depende N, y más que O(N)tiempo (en términos de su dependencia de N), que tenemos la intención de mejorar.
SirGuy
@SirGuy Agradezco su preocupación por el concepto de probeta y el costo de la memoria de procesamiento paralelo. Mi publicación es compartir mis pensamientos sobre el problema. Los procesadores de GPU ahora están haciendo un procesamiento paralelo posible. Quién sabe, si el concepto de probeta no estará disponible en el futuro.
shuva