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

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个缺失的数字。


当前回答

我让一个4岁的孩子来解决这个问题。他把数字分类,然后开始数。这有一个O(厨房地板)的空间要求,它的工作就像许多球丢失一样简单。

其他回答

    //sort
    int missingNum[2];//missing 2 numbers- can be applied to more than 2
    int j = 0;    
    for(int i = 0; i < length - 1; i++){
        if(arr[i+1] - arr[i] > 1 ) {
            missingNum[j] = arr[i] + 1;
            j++;
        }
    }

你可以试试布卢姆滤镜。将袋子中的每个数字插入到bloom中,然后遍历完整的1-k集,直到报告每个数字都没有找到。这可能不是在所有情况下都能找到答案,但可能是一个足够好的解决方案。

还有一种方法是使用残差图滤波。

假设数字1到4少了3。二进制表示如下:

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

我可以创建一个像下面这样的流程图。

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

注意,流图包含x个节点,而x是比特数。最大边数是(2*x)-2。

因此,对于32位整数,它将占用O(32)空间或O(1)空间。

现在如果我从1,2,4开始移除每个数的容量那么我就剩下了一个残差图。

0 ----------> 1 ---------> 1

最后我将像下面这样运行一个循环,

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

现在的结果是结果中包含的数字也没有缺失(假阳性)。但是当有k个缺失元素时,k <=(结果的大小)<= n。

我将最后一次检查给定的列表,以标记缺少或没有的结果。

所以时间复杂度是O(n)

最后,可以通过选取节点00、01、11、10而不是0和1来减少误报的数量(以及所需的空间)。

对于Q2,这是一个比其他解决方案效率更低的解决方案,但仍然有O(N)个运行时和O(k)个空间。

这个想法是运行原始算法两次。在第一个例子中,你得到了缺失的总数,这给了你缺失数字的上界。我们称这个数为N,你知道这两个数的和是N,所以第一个数只能在[1,floor((N-1)/2)]区间内,而第二个数将在[floor(N/2)+1,N-1]区间内。

因此,再次循环所有数字,丢弃第一个间隔中不包括的所有数字。你可以记录它们的和。最后,你将知道丢失的两个数字中的一个,进而知道第二个数字。

我有一种感觉,这种方法可以被推广,也许在一次输入传递期间,多个搜索可以“并行”运行,但我还没有弄清楚如何做到这一点。

您可能需要澄清O(k)的含义。

这里有一个任意k的简单解:对于你的数字集中的每一个v,将2^v相加。最后,循环i从1到n,如果和2^i按位和为零,则i缺失。(或者在数字上,如果和的底除以2^i是偶数。或者模2^(i+1) < 2^i

容易,对吧?O(N)时间,O(1)存储,支持任意k。

除了你在计算一个巨大的数字,在真正的计算机上,每个数字都需要O(N)个空间。事实上,这个解和位向量是一样的。

所以你可以很聪明地计算和,平方和和和立方体的和…直到v^k的和,然后用复杂的数学方法提取结果。但这些都是很大的数字,这就引出了一个问题:我们谈论的是哪种抽象的运作模式?O(1)空间中有多少是合适的,以及需要多长时间才能将所需大小的数字相加?