Bestimmen Sie die fehlende Nummer im Datenstrom

14

Wir erhalten einen Strom von paarweise unterschiedlichen Zahlen aus der Menge .n1{1,,n}

Wie kann ich die fehlende Zahl mit einem Algorithmus ermitteln, der den Stream einmal liest und nur einen Speicher von Bits verwendet?O(log2n)

Warteschlange
quelle

Antworten:

7

Sie wissen , dass i=1ni=n(n+1)2 und weilS=n(n+1)2 konnte in codierter werdenO(log(n))Bits dies getan werden kannO(logn)Speicher und in einem Weg (nur findenScurrentSum, dies fehlt Zahl).

Aber dieses Problem könnte im allgemeinen Fall (für die Konstante ) gelöst werden : Wir haben k fehlende Zahlen, finden Sie alle heraus. In diesem Fall, anstatt nur die Summe von y i zu berechnen, berechnen Sie die Summe der j'sten Potenz von x i für alle 1 j k (ich nahm an, dass x i fehlende Zahlen und y i eingegebene Zahlen sind):kkyixich1jkxichyich

ich=1kxich=S1,ich=1kxich2=S2,ich=1kxichk=Sk (1)

Denken Sie daran , dass Sie berechnen können , einfach, weil S 1 = S - y i , S 2 = i 2 - y 2 i , ...S1,...SkS1=S-yichS2=ich2-yich2

Um nun fehlende Zahlen zu finden, müssen Sie lösen , um alle x i zu finden .(1)xich

Sie können berechnen:

, P 2 = x ix j , ..., P k = x i ( 2 ) .P1=xichP2=xichxjPk=xich (2)

Beachten Sie dazu , dass , P 2 = S 2 1 - S 2P1=S1 , ...P2=S12-S22

Aber ist Koeffizienten von P = ( x - x 1 ) ( x - x 2 ) ( x - x k ) aber P berücksichtigt werden kann eindeutig, so dass Sie fehlende Zahlen finden.PichP=(x-x1)(x-x2)(x-xk)P

Das sind nicht meine Gedanken; lies das .

Raphael
quelle
1
Ich verstehe nicht (2). Vielleicht, wenn Sie in den Summen Details hinzugefügt? Vermisst ein ? Pk
Raphael
@Raphael, ist Newtons Identität. Wenn Sie sich meine referenzierte Wiki-Seite ansehen, können Sie sich eine Vorstellung von der Berechnung machen. Jedes P i könnte durch vorherige P s, S j berechnet werden. Erinnern Sie sich an die einfache Formel: 2 x 1x 2 = ( x 1 + x 2 ) 2 - ( x 2 1 + x 2 2 ) , können Sie auf alle Potenzen einen ähnlichen Ansatz anwenden. Auch als ich P i schriebPiPiPSj2x1x2=(x1+x2)2(x12+x22)Piist Sigma von etwas, aber hat kein Σ , weil es nur ein Π gibt . PkΣΠ
Wie dem auch sei, die Antworten sollten in angemessenem Maße in sich geschlossen sein. Sie geben einige Formeln an, warum sollten Sie sie nicht vervollständigen?
Raphael
11

Aus dem obigen Kommentar:

Before processing the stream, allocate log2n bits, in which you write x:=i=1nbin(i) (bin(i) is the binary representation of i and is pointwise exclusive-or). Naively, this takes O(n) time.

Berechnen Sie nach der Verarbeitung des Streams immer dann, wenn man eine Zahl liest , x : = x b i n ( j ) . Lassen Sie k die Zahlen von seinem { 1 , . . . n } , das nicht im Stream enthalten ist. Nachdem wir den gesamten Strom gelesen haben, haben wir x = ( n i = 1 b i n ( i ) )( i k bjx:=xbin(j)k{1,...n} das gewünschte Ergebnis ergibt.

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

Daher haben wir verwendet und haben eine Gesamtlaufzeit von O ( n ) .O(logn)O(n)

HdM
quelle
3
Darf ich eine einfache Optimierung vorschlagen, die dies zu einem echten Streaming-Single-Pass-Algorithmus macht: im Zeitschritt ichxor x mit bichn(ich) und mit der Eingabe bichn(j)das ist im Stream angekommen. Dies hat den zusätzlichen Vorteil, dass Sie es auch dann zum Laufen bringen können, wennn ist nicht im Voraus bekannt: Beginnen Sie einfach mit einem einzelnen Bit, das für reserviert ist x und "vergrößern" Sie den zugewiesenen Speicherplatz nach Bedarf.
Sasho Nikolov
0

HdM's solution works. I coded it in C++ to test it. I can't limit the value to O(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
quelle
3
Bitte posten Sie stattdessen lesbaren (Pseudo-) Code nur des Algorithmus (Skip Main). Außerdem sollte ein Korrektheitsbeweis / Argument auf einer bestimmten Ebene enthalten sein.
Raphael
4
@edA-qamort-ora-y Your answer assumes that the reader knows C++. To someone who is not familiar with this language, there is nothing to see: both finding the relevant passage and understanding what it's doing are a challenge. Readable pseudocode would make this a better answer. The C++ is not really useful on a computer science site.
Gilles 'SO- stop being evil'
3
Wenn sich meine Antwort als nicht nützlich erweist, müssen die Leute nicht dafür stimmen.
edA-qa mort-ora-y
2
+1, wenn Sie sich die Zeit genommen haben, C ++ - Code zu schreiben und ihn zu testen. Leider, wie andere betonten, ist es nicht so. Sie geben sich dennoch Mühe!
Julien Lebot
9
Ich verstehe den Sinn dieser Antwort nicht: Sie nehmen die Lösung eines anderen, die sehr einfach und offensichtlich sehr effizient ist, und "testen" sie. Warum ist ein Test notwendig? Dies ist wie ein Test, bei dem Ihr Computer Zahlen korrekt hinzufügt. Und es gibt auch nichts Nicht-Triviales an Ihrem Code.
Sasho Nikolov