Determinar el número faltante en la secuencia de datos

14

Recibimos una secuencia de pares diferentes números del conjunto { 1 , ... , n } .norte-1{1,...,norte}

¿Cómo puedo determinar el número faltante con un algoritmo que lee la secuencia una vez y usa una memoria de solo bits?O(Iniciar sesión2norte)

Cola
fuente

Respuestas:

7

Sabes , y porqueS=n(n+1)i=1ni=n(n+1)2 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).S=n(n+1)2O(log(n))O(logn)ScurrentSum

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 xkkyixi1jk faltan números e y i son números de entrada):xiyi

i=1kxi=S1,i=1kxi2=S2,i=1kxik=Sk (1)

Recuerde que puede calcular simplemente, porque S 1 = S - y i , S 2 = i 2 - y 2 i , ...S1,...SkS1=SyiS2=i2yi2

Ahora, para encontrar números que faltan, debes resolver para encontrar todo x i .(1)xi

Puedes calcular:

, P 2 = x ix j , ..., P k = xP1=xiP2=xixj ( 2 ) .Pk=xi (2)

Para esto recuerde que , P 2 = S 2 1 - S 2P1=S1 , ...P2=S12S22

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.PiP=(xx1)(xx2)(xxk)P

Estos no son mis pensamientos; leer este .

Rafael
fuente
1
No entiendo (2). ¿Tal vez si agregaste los detalles de las sumas? ¿ pierde un ? Pk
Raphael
@Raphael, es la identidad de Newton, creo que si echas un vistazo a mi página wiki referenciada puedes tener la idea del cálculo, cada P i podría calcularse por P s, S j anteriores , recuerda la fórmula simple: 2 x 1x 2 = ( x 1 + x 2 ) 2 - ( x 2 1 + x 2 2 ) , puede aplicar un enfoque similar a todas las potencias. También como escribí P iPiPiPSj2x1x2=(x1+x2)2(x12+x22)Pi es sigma de algo, pero no tiene ningún Σ , porque solo hay uno Π . PkΣΠ
Sea como fuere, las respuestas deben ser independientes en un grado razonable. Usted da algunas fórmulas, entonces ¿por qué no completarlas?
Raphael
11

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.log2nx:=i=1nbin(i)bin(i)iO(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 bjx:=xbin(j)k{1,...n} produciendo el resultado deseado.

x=(i=1nbin(i))(ikbin(i))=bin(k)ik(bin(i)bin(i))=bin(k),

Por lo tanto, utilizamos el espacio y tenemos un tiempo de ejecución general de O ( n ) .O(logn)O(n)

HdM
fuente
3
ixbin(i)bin(j)nx
0

La solución de HdM funciona. Lo codifiqué en C ++ para probarlo. No puedo limitar elvalueO(log2n) bits, but I'm sure you can easily show how only that number of bits is actually set.

For those that want pseudo code, using a simple fold operation with exclusive or ():

Missing=fold(,{1,,N}InputStream)

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 xx=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.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

void find_missing( int const * stream, int len );

int main( int argc, char ** argv )
{
    if( argc < 2 )
    {
        cerr << "Syntax: " << argv[0] << " N" << endl;
        return 1;
    }
    int n = atoi( argv[1] );

    //construct sequence
    vector<int> seq;
    for( int i=1; i <= n; ++i )
        seq.push_back( i );

    //remove a number and remember it
    srand( unsigned(time(0)) );
    int remove = (rand() % n) + 1;
    seq.erase( seq.begin() + (remove - 1) );
    cout << "Removed: " << remove << endl;

    //give the stream a random order
    std::random_shuffle( seq.begin(), seq.end() );

    find_missing( &seq[0], int(seq.size()) );
}

//HdM's solution
void find_missing( int const * stream, int len )
{
    //create initial value of n sequence xor'ed (n == len+1)
    int value = 0;
    for( int i=0; i < (len+1); ++i )
        value = value ^ (i+1);

    //xor all items in stream
    for( int i=0; i < len; ++i, ++stream )
        value = value ^ *stream;

    //what's left is the missing number
    cout << "Found: " << value << endl;
}
edA-qa mort-ora-y
fuente
3
Please post readable (pseudo) code of only the algorithm instead (skip main). Also, a correctness proof/argument at some level should be included.
Raphael
4
@ edA-qamort-ora-y Su respuesta supone que el lector conoce C ++. Para alguien que no está familiarizado con este lenguaje, no hay nada que ver: tanto encontrar el pasaje relevante como comprender lo que está haciendo es un desafío. El pseudocódigo legible haría de esta una mejor respuesta. El C ++ no es realmente útil en un sitio de informática.
Gilles 'SO- deja de ser malvado'
3
Si mi respuesta demuestra que no es útil, la gente no necesita votar por ella.
edA-qa mort-ora-y
2
+1 por tomarse el tiempo para escribir código C ++ y probarlo. Desafortunadamente, como otros señalaron, no es TAN. ¡Todavía pones esfuerzo en esto!
Julien Lebot
99
No entiendo el punto de esta respuesta: tomas la solución de otra persona, que es muy simple y obviamente muy eficiente, y la "pruebas". ¿Por qué son necesarias las pruebas? Esto es como probar que su computadora agrega números correctamente. Y tampoco hay nada no trivial sobre su código.
Sasho Nikolov