Determinar o número ausente no fluxo de dados

14

Recebemos um fluxo de pares diferentes de números do conjunto { 1 , , n } .n1{1,,n}

Como posso determinar o número ausente com um algoritmo que lê o fluxo uma vez e usa uma memória de apenas bits?O(log2n)

Fila
fonte

Respostas:

7

Você sabe e porqueS=n(n+1)i=1ni=n(n+1)2 pode ser codificado embitsO(log(n)),isso pode ser feito namemóriaO(logn)e em um caminho (basta encontrarS-currentSum, esse número está faltando).S=n(n+1)2O(log(n))O(logn)ScurrentSum

Mas esse problema pode ser resolvido no caso geral (para a constante ): temos k números ausentes, descubra todos eles. Nesse caso, em vez de calcular apenas a soma de y i , calcule a soma da j'st de x i para todos os 1 j k (assumi que x i está faltando números e y i é um número de entrada):kkyixi1jkxiyEu

Eu=1kxEu=S1,Eu=1kxEu2=S2,Eu=1kxEuk=Sk (1)

Lembre-se que você pode calcular simplesmente, porque S 1 = S - Σ y i , S 2 = Σ i 2 - Σ Y 2 i , ...S1,...SkS1=S-yEuS2=Eu2-yEu2

Agora, para encontrar números ausentes, você deve resolver para encontrar todos os x i .(1)xi

Você pode calcular:

, P 2 = x ix j , ..., P k = x i ( 2 ) .P1=xEuP2=xEuxjPk=xEu (2)

Para isso, lembre-se de que , P 2 = S 2 1 - S 2P1=S1 ...P2=S12-S22

Mas é coeficiente de P = ( x - x 1 ) ( x - x 2 ) ( x - x k ), mas P pode ser fatorado exclusivamente, para que você possa encontrar números ausentes.PEuP=(x-x1)(x-x2)(x-xk)P

Estes não são meus pensamentos; leia isso .

Rafael
fonte
1
Eu não entendo (2). Talvez se você adicionou os detalhes das somas? Does perder um Σ ? Pk
Raphael
@Raphael, é a identidade de Newton, acho que se você der uma olhada na minha página wiki referenciada, pode ter uma idéia de cálculo, cada P i pode ser calculado por P s, S j anteriores , lembre-se da fórmula simples: 2 x 1x 2 = ( x 1 + x 2 ) 2 - ( x 2 1 + x 2 2 ) , você pode aplicar uma abordagem semelhante a todos os poderes. Também como eu escrevi P iPEuPEuPSj2x1x2=(x1+x2)2-(x12+x22)PEué sigma de alguma coisa, mas não tem nenhum Σ , porque existe apenas um Π . PkΣΠ
Seja como for, as respostas devem ser independentes em um grau razoável. Você fornece algumas fórmulas, então por que não fazê-las completas?
Raphael
11

Do comentário acima:

Antes de processamento da corrente, alocar bits, onde escrever x : = n i = 1 b i n ( i ) ( b i n ( i ) é a representação binária de i e é pontual exclusive- ou). Ingenuamente, isso leva tempo O ( n ) .registro2nx: =Eu=1nbEun(Eu)bEun(Eu)EuO(n)

Ao processar o fluxo, sempre que alguém ler um número , calcule x : = x b i n ( j ) . Vamos k ser o número único de { 1 , . . . n } que não está incluído no fluxo. Depois de ler todo o fluxo, temos x = ( n i = 1 b i n ( i ) )( i k bjx: =xbEun(j)k{1,...n} obtendo-se o resultado desejado.

x=(Eu=1nbEun(Eu))(EukbEun(Eu))=bEun(k)Euk(bEun(Eu)bEun(Eu))=bEun(k),

Portanto, usamos espaço e temos um tempo de execução geral de O ( n ) .O(registron)O(n)

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

valueO(registro2n)

dobra

Ausência de=dobra(,{1,...,N}InputStream)

O(registro2n)xx=0 0

#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
fonte
3
Poste um código legível (pseudo) apenas do algoritmo (pule principal). Além disso, uma prova / argumento de correção em algum nível deve ser incluído.
Raphael
4
@ edA-qamort-ora-y Sua resposta assume que o leitor conhece C ++. Para alguém que não está familiarizado com esse idioma, não há nada para ver: encontrar a passagem relevante e entender o que está fazendo é um desafio. O pseudocódigo legível tornaria essa uma resposta melhor. O C ++ não é realmente útil em um site de ciência da computação.
Gilles 'SO- stop be evil'
3
Se minha resposta não for útil, as pessoas não precisam votar nela.
edA-qa mort-ora-y
2
+1 por escrever um código C ++ e testá-lo. Infelizmente, como outros apontaram, não é assim. Ainda você se esforça nisso!
Julien Lebot
9
Não entendi o ponto desta resposta: você pega a solução de outra pessoa, que é muito simples e obviamente muito eficiente, e a "testa". Por que o teste é necessário? É como testar se o computador adiciona números corretamente. E também não há nada não trivial no seu código.
Sasho Nikolov