我有一段时间有一个有趣的面试经历.问题开始很简单:
Q1:我们有包含数字的袋子
1,2,3,...,100.每个数字只出现一次,因此有100个数字.现在从包里随机挑出一个号码.找到丢失的号码.
当然,我之前听过这个采访问题,所以我很快回答了以下问题:
A1:嗯,这些数字的总和
1 + 2 + 3 + … + N是(N+1)(N/2)(见维基百科:算术系列之和).因为N = 100,总和是5050.因此,如果包中存在所有数字,则总和将是精确的
5050.由于缺少一个数字,总和将小于此数值,差异就是该数字.所以我们可以在O(N)时间和O(1)空间中找到丢失的数字.
在这一点上,我认为我做得很好,但突然之间,这个问题发生了意想不到的变化:
Q2:这是正确的,但是现在如果缺少两个数字你会怎么做？
我之前从未见过/听过/考虑过这种变化,所以我惊慌失措,无法回答这个问题.面试官坚持要知道我的思考过程,所以我提到也许我们可以通过与预期产品进行比较来获得更多信息,或者可能在从第一遍获得一些信息后再做第二遍,但我真的只是拍摄在黑暗中而不是实际上有一条清晰的解决方案.
面试官确实试图鼓励我说有第二个等式确实是解决问题的一种方法.在这一点上,我有点不高兴(因为事先不知道答案),并询问这是一般的(阅读:"有用")编程技术,还是只是一个技巧/问题答案.
面试官的回答让我感到惊讶:你可以概括一下找到3个缺失数字的技巧.实际上,您可以将其概括为找到k个缺失的数字.
Qk:如果行李中缺少k个号码,您会如何有效地找到它？
这是几个月前,我仍然无法弄清楚这种技术是什么.显然有一个?(N)时间下限,因为我们必须扫描所有数字至少一次,但是访问者坚持解决技术的时间和空间复杂度(减去O(N)输入扫描的时间)在k而不是N中定义.
所以这里的问题很简单: