Recibimos una secuencia de pares diferentes números del conjunto { 1 , ... , n } .
¿Cómo puedo determinar el número faltante con un algoritmo que lee la secuencia una vez y usa una memoria de solo bits?
Recibimos una secuencia de pares diferentes números del conjunto { 1 , ... , n } .
¿Cómo puedo determinar el número faltante con un algoritmo que lee la secuencia una vez y usa una memoria de solo bits?
Sabes , y porqueS=n(n+1) podría codificarse enbitsO(log(n))esto se puede hacer en lamemoriaO(logn)y en una ruta (solo encuentreS-currentSum, este es el número que falta).
Pero este problema podría resolverse en un caso general (para constante ): tenemos k números que faltan, descúbrelos todos. En este caso, en lugar de calcular solo la suma de y i , calcule la suma de j'st potencia de x i para todo 1 ≤ j ≤ k (supuse x faltan números e y i son números de entrada):
Recuerde que puede calcular simplemente, porque S 1 = S - ∑ y i , S 2 = ∑ i 2 - ∑ y 2 i , ...
Ahora, para encontrar números que faltan, debes resolver para encontrar todo x i .
Puedes calcular:
, P 2 = ∑ x i ⋅ x j , ..., P k = ∏ x ( 2 ) .
Para esto recuerde que , P 2 = S 2 1 - S 2 , ...
Pero son coeficientes de P = ( x - x 1 ) ⋅ ( x - x 2 ) ⋯ ( x - x k ), pero P podría factorizarse únicamente, por lo que puede encontrar los números que faltan.
Estos no son mis pensamientos; leer este .
Del comentario anterior:
Antes de procesar el flujo, asigne bits, en el que escriba x : = ⨁ n i = 1 b i n ( i ) ( b i n ( i ) es la representación binaria de i y ⊕ es exclusivo de pointwise- o). Ingenuamente, esto lleva O ( n ) tiempo.⌈log2n⌉ x:=⨁ni=1bin(i) bin(i) i ⊕ O(n)
Al procesar la secuencia, cada vez que uno lea un número , calcule x : = x ⊕ b i n ( j ) . Deje que k es el número único de { 1 , . . . n } que no está incluido en la secuencia. Después de haber leído todo el flujo, tenemos x = ( n ⨁ i = 1 b i n ( i ) ) ⊕ ( ⨁ i ≠ k bj x:=x⊕bin(j) k {1,...n}
produciendo el resultado deseado.
Por lo tanto, utilizamos el espacio y tenemos un tiempo de ejecución general de O ( n ) .O(logn) O(n)
fuente
La solución de HdM funciona. Lo codifiqué en C ++ para probarlo. No puedo limitar elO(log2n) bits, but I'm sure you can easily show how only that number of bits is actually set.
value
For those that want pseudo code, using a simplefold operation with exclusive or (⊕ ):
Hand-wavey proof: A⊕ never requires more bits than its input, so it follows that no intermediate result in the above requires more than the maximum bits of the input (so O(log2n) bits). ⊕ is commutative, and x⊕x=0 , thus if you expand the above and pair off all data present in the stream you'll be left only with a single un-matched value, the missing number.
fuente