简单的面试问题变得更难了:给定数字1..100，在给定k个缺失数的情况下找出缺失数

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

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

当前回答

如果一个数字只出现一次，用下面的方法很容易分辨:

创建一个大小为给定数字的布尔数组boolArray;这里是100。

遍历输入数字，并根据数字值将一个元素设置为true。例如，如果找到45，则设置boolArray[45-1] = true;

这是一个O(N)运算。

然后循环遍历boolArray。如果一个元素保持为false，那么element + 1的下标就是缺失的数字。例如，如果boolArray[44]为false，我们就知道第45号丢失了。

这是O(n)运算。空间复杂度为O(1)。

所以这个解可以从一个给定的连续数集中找到任何缺失的数。

2012-08-17 18:25:22

其他回答

    //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++;
        }
    }

2015-10-12 01:46:33

免责声明:我已经读了这个问题好几天了，但我的知识超出了我对数学的理解。

我试着用set来解决它:

arr=[1,2,4,5,7,8,10] # missing 3,6,9
NMissing=3
arr_origin = list(range(1,arr[-1]+1))

for i in range(NMissing):
      arr.append(arr[-1]) ##### assuming you do not delete the last one

arr=set(arr)
arr_origin=set(arr_origin)
missing=arr_origin-arr # 3 6 9

2017-01-17 06:39:38

假设一个ArrayList对象(myList)被这些数字填充，其中x和y两个数字缺失。所以可能的解决方案是:

int k = 1;
        while (k < 100) {
            if (!myList.contains(k)) {
                System.out.println("Missing No:" + k);
            }
            k++;
        }

2019-07-06 19:47:37

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

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

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

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

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

2010-08-16 10:37:28

如果一个数字只出现一次，用下面的方法很容易分辨:

创建一个大小为给定数字的布尔数组boolArray;这里是100。

遍历输入数字，并根据数字值将一个元素设置为true。例如，如果找到45，则设置boolArray[45-1] = true;

这是一个O(N)运算。

然后循环遍历boolArray。如果一个元素保持为false，那么element + 1的下标就是缺失的数字。例如，如果boolArray[44]为false，我们就知道第45号丢失了。