确定数据流中的丢失数字

Question

我们从集合$ left {1， dots，n right } $中收到$ n-1 $成对不同的数字的流。

如何使用读取流一次并仅使用$ o（ log_2 n）$位的内存的算法来确定丢失的数字？

Answer 1

您知道$ sum_ {i = 1}^ni = frac {n（n+1）} {2} $，因为$ s = frac {n（n+1）} {2} {2} $可以被编码在$ o（ log（n））$ bits中，这可以在$ o（ log n）$内存和一条路径中完成（只需找到$ s- mathrm {currentum} $，这是丢失的数字）。

但是，在通常的情况下，可以解决此问题（对于常数$ k $）：我们有$ k $丢失的数字，请找出所有数字。在这种情况下，而不是仅计算$ y_i $的总和，计算$ x_i $的$ x_i $的总和，$ x_i $的所有$ 1 le j le k $（我假设$ x_i $是丢失的数字，$ y_i $ is INPUT NUMBER ）：

美元sum_ {i = 1}^k x_i^k＆= s_k end {align} $ $ $ qquad（1）$

请记住，您可以计算$ s_1，... s_k $简单，因为$ s_1 = s- sum y_i $，$ s_2 = sum i^2 - sum y_i^2 $，...

现在，要查找丢失的数字，您应该解决$（1）$找到所有$ x_i $。

您可以计算：

$ p_1 = sum x_i $，$ p_2 = sum x_i cdot x_j $，...，$ p_k = prod x_i $ $（2）$。

为了这 记住这一点 $ p_1 = s_1 $，$ p_2 = frac {s_1^2 -s_2} {2} $，...

但是$ p_i $是$ p =（x-x_1）的系数 可以考虑 独特，因此您可以找到丢失的数字。

这些不是我的想法；读 这个.

Answer 2

从上面的评论：

在处理流之前，请分配$ lceil log_2 n rceil $ bit，其中写入$ x：= bigoplus_ {i = 1}^n n mathrm {bin}（bin}（i）$（$ mathrm {bin} （i）$是$ i $的二进制表示形式，而$ oplus $ inpointwise独家或）。天真地，这需要$ Mathcal {o}（n）$时间。

处理流后，每当读取数字$ j $时，计算$ x：= x oplus mathrm {bin}（j）$。令$ k $为$ {1，... n } $的单个数字，该数字未包含在流中。阅读了整个流后，我们有$$ x = left（ bigoplus_ {i = 1}^n mathrm {bin}（i） right） oplus left（ bigoplus_ {i neq k} mathrm {bin}（i） right）= mathrm {bin}（k） oplus bigoplus_ {i neq k}（ mathrm {bin}（i） mathrm {bin}（k），$$产生所需的结果。

因此，我们使用了$ Mathcal {o}（ log n）$ space，并具有$ MATHCAL {O}（n）$的总运行时。

Answer 3

HDM的解决方案有效。我在C ++中对其进行了编码以对其进行测试。我不能限制 value 到$ o（ log_2 n）$ bits，但我敢肯定，您可以轻松地显示如何实际设置该数量的位。

对于那些想要伪代码的人，使用独家或（$ oplus $）的简单$ text {fold} $操作：

$$ text {丢失} = text {fold}（ oplus， {1， ldots，n } cup text {inputStream}）$$

手动波动证明：一个$ oplus $永远不需要比其输入更多的位，因此可以遵循以上不需要的中间结果，需要超过输入的最大位（因此$ o（ log_2 n）$位）。 $ oplus $是可交换的，$ x oplus x = 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;
}