前段时间我有一次有趣的面试经历。问题一开始很简单:

Q1:我们有一个袋子,里面有数字1,2,3,…,100。每个数字恰好出现一次,所以有100个数字。现在从袋子里随机抽取一个数字。找到丢失的号码。

当然,我以前听过这个面试问题,所以我很快就回答了这个问题:

A1:嗯,1 + 2 + 3 +…+ N的和是(N+1)(N/2)(参见维基百科:等差级数的和)。当N = 100时,和是5050。 因此,如果所有的数字都在袋子里,总和将恰好是5050。因为少了一个数,总和就会小于这个数,差的就是这个数。所以我们可以在O(N)时间和O(1)空间中找到这个缺失的数。

在这一点上,我认为我做得很好,但突然间,问题发生了意想不到的转变:

这是正确的,但是如果少了两个数字,你会怎么做?

我以前从未见过/听过/考虑过这种变化,所以我很恐慌,无法回答这个问题。面试官坚持要知道我的思考过程,所以我提到,也许我们可以通过与预期产品进行比较来获得更多信息,或者在从第一次传递中收集到一些信息后再进行第二次传递,等等,但我真的只是在黑暗中拍摄,而不是真正有一个明确的解决方案的路径。

面试官试图鼓励我说,有第二个方程确实是解决问题的一种方法。在这一点上,我有点不安(因为事先不知道答案),并问这是一种通用的(阅读:“有用的”)编程技术,还是只是一个技巧/答案。

面试官的回答让我惊讶:你可以把这个技巧概括为3个缺失的数字。事实上,你可以推广它来找到k个缺失的数。

Qk:如果袋子里少了k个数字,你如何有效地找到它?

这是几个月前的事了,我还不明白这个技巧是什么。显然有一个Ω(N)的时间下限,因为我们必须扫描所有的数字至少一次,但面试官坚持认为,解决技术的时间和空间复杂度(减去O(N)次输入扫描)定义为k而不是N。

所以问题很简单:

如何解决Q2? 你会如何解决Q3? 如何求解Qk?


澄清

Generally there are N numbers from 1..N, not just 1..100. I'm not looking for the obvious set-based solution, e.g. using a bit set, encoding the presence/absence each number by the value of a designated bit, therefore using O(N) bits in additional space. We can't afford any additional space proportional to N. I'm also not looking for the obvious sort-first approach. This and the set-based approach are worth mentioning in an interview (they are easy to implement, and depending on N, can be very practical). I'm looking for the Holy Grail solution (which may or may not be practical to implement, but has the desired asymptotic characteristics nevertheless).

当然,你必须以O(N)为单位扫描输入,但你只能捕获少量的信息(用k而不是N定义),然后必须以某种方式找到k个缺失的数字。


当前回答

你能查一下每个号码是否都存在吗?如果是,你可以试试这个:

S =袋子中所有数字的和(S < 5050) Z =缺失数的和5050 - S

如果缺失的数字是x和y,则:

x = Z - y和 max(x) = Z - 1

所以你检查从1到max(x)的范围,并找到这个数字

其他回答

一种方法是对质数101取模。

计算并存储整数1到100的乘积,对该数字取101的模。小外显:结果是1。

计算并存储所有数字1到100的和,对结果对101进行模运算。小exo:结果是0。

现在假设袋子里的数字x和y都被拿走了。

求包里所有东西对101模的乘积和。这样我就知道的值

A = x+y和 b = x * y

modulo 101。

现在很容易求出x和y对101的模(求解含有101个元素的有限域上的二次多项式)。

现在你知道了x和y对101的模。但是因为你知道x和y都小于101,所以你知道它们的真实值。

这里有一个解决方案,使用k位额外的存储空间,没有任何聪明的技巧,只是简单。执行时间O (n),额外空间O (k)。只是为了证明这个问题可以解决,而不需要先阅读解决方案或成为天才:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

不确定,这是否是最有效的解决方案,但我会遍历所有条目,并使用bitset来记住,设置了哪些数字,然后测试0位。

我喜欢简单的解决方案,我甚至相信,它可能比计算和,或平方和等更快。

也许这个算法可以解决问题1:

预计算前100个整数的xor (val=1^2^3^4....100) 对来自输入流的元素进行Xor (val1=val1^next_input) 最终的答案= val ^ val1

或者更好:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

这个算法实际上可以扩展到两个缺失的数字。第一步还是一样。当我们调用缺少两个数字的GetValue时,结果将是a1^a2是缺少的两个数字。让说

跌倒 = a1^a2

Now to sieve out a1 and a2 from val we take any set bit in val. Lets say the ith bit is set in val. That means that a1 and a2 have different parity at ith bit position. Now we do another iteration on the original array and keep two xor values. One for the numbers which have the ith bit set and other which doesn't have the ith bit set. We now have two buckets of numbers, and its guranteed that a1 and a2 will lie in different buckets. Now repeat the same what we did for finding one missing element on each of the bucket.

有一个通用的方法来解决这样的流问题。 我们的想法是使用一些随机化,希望将k个元素“分散”到独立的子问题中,在那里我们的原始算法为我们解决了问题。该技术用于稀疏信号重建等。

创建一个大小为u = k^2的数组a。 选取任意通用哈希函数h:{1,…,n} ->{1,…,u}。(如multiply-shift) 对于1中的每一个i,…, n增加a[h(i)] += i 对于输入流中的每个数字x,减去a[h(x)] -= x。

如果所有缺失的数字都已散列到不同的bucket中,则数组的非零元素现在将包含缺失的数字。

根据通用哈希函数的定义,特定对被发送到同一桶的概率小于1/u。由于大约有k^2/2对,我们有错误概率不超过k^2/2/u=1/2。也就是说,我们成功的概率至少是50%,如果我们增加u,我们的机会就会增加。

注意,这个算法占用k^2 logn位的空间(每个数组桶需要logn位)。这与@Dimitris Andreou的答案所需要的空间相匹配(特别是多项式因式分解的空间要求,它碰巧也是随机的。) 该算法每次更新的时间也是常数,而不是幂和情况下的时间k。

事实上,通过使用评论中描述的技巧,我们甚至可以比幂和法更有效。