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

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


当前回答

我相信我有一个O(k)时间和O(log(k)空间算法,前提是你有任意大整数的下限(x)和log2(x)函数:

你有一个k位的长整数(因此是log8(k)空间),其中你加上x^2,其中x是你在袋子里找到的下一个数字:s=1^2+2^2+…这需要O(N)时间(这对面试官来说不是问题)。最后得到j= (log2(s))这是你要找的最大的数。然后s=s-j,重复上面的步骤:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

现在,对于2756位的整数,通常没有floor和log2函数,而是用于double。所以呢?简单地说,对于每2个字节(或1、3、4),您可以使用这些函数来获得所需的数字,但这增加了O(N)因素的时间复杂度

其他回答

非常好的问题。我会用Qk的集合差。很多编程语言甚至都支持它,比如Ruby:

missing = (1..100).to_a - bag

这可能不是最有效的解决方案,但如果我在这种情况下面临这样的任务(已知边界,低边界),这是我在现实生活中会使用的解决方案。如果数字集非常大,那么我当然会考虑一个更有效的算法,但在此之前,简单的解决方案对我来说已经足够了。

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

You can motivate the solution by thinking about it in terms of symmetries (groups, in math language). No matter the order of the set of numbers, the answer should be the same. If you're going to use k functions to help determine the missing elements, you should be thinking about what functions have that property: symmetric. The function s_1(x) = x_1 + x_2 + ... + x_n is an example of a symmetric function, but there are others of higher degree. In particular, consider the elementary symmetric functions. The elementary symmetric function of degree 2 is s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n, the sum of all products of two elements. Similarly for the elementary symmetric functions of degree 3 and higher. They are obviously symmetric. Furthermore, it turns out they are the building blocks for all symmetric functions.

你可以通过注意s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1))来构建初等对称函数。进一步思考应该会使您相信s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))等等,因此它们可以在一次传递中计算。

我们如何知道数组中缺少了哪些项?考虑多项式(z-x_1) (z-x_2)……(z-x_n)。如果你输入任意一个数字x_i,它的值都是0。展开多项式,得到z^n-s_1(x)z^(n-1)+。+ (-1)^n s_n。初等对称函数也出现在这里,这并不奇怪,因为多项式应该保持不变,如果我们对根进行任何排列。

所以我们可以建立一个多项式,并尝试因式分解来找出哪些数不在集合中,就像其他人提到的那样。

Finally, if we are concerned about overflowing memory with large numbers (the nth symmetric polynomial will be of the order 100!), we can do these calculations mod p where p is a prime bigger than 100. In that case we evaluate the polynomial mod p and find that it again evaluates to 0 when the input is a number in the set, and it evaluates to a non-zero value when the input is a number not in the set. However, as others have pointed out, to get the values out of the polynomial in time that depends on k, not N, we have to factor the polynomial mod p.

我还没有检查数学,但我怀疑在计算Σ(n)的同时计算Σ(n^2)将提供足够的信息来得到两个缺失的数字,如果有三个,也要计算Σ(n^3),等等。

我相信我有一个O(k)时间和O(log(k)空间算法,前提是你有任意大整数的下限(x)和log2(x)函数:

你有一个k位的长整数(因此是log8(k)空间),其中你加上x^2,其中x是你在袋子里找到的下一个数字:s=1^2+2^2+…这需要O(N)时间(这对面试官来说不是问题)。最后得到j= (log2(s))这是你要找的最大的数。然后s=s-j,重复上面的步骤:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

现在,对于2756位的整数,通常没有floor和log2函数,而是用于double。所以呢?简单地说,对于每2个字节(或1、3、4),您可以使用这些函数来获得所需的数字,但这增加了O(N)因素的时间复杂度