我有一段时间有一个有趣的面试经历.问题开始很简单:
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中定义.
所以这里的问题很简单:
我有一个从1到100(包括两者)的数字数组.数组的大小为100.数字随机添加到数组中,但数组中有一个随机空插槽.找到该插槽的最快捷方式是什么,以及插入插槽的数量是多少？Java解决方案更可取.
你怎么做到这一点？值未排序但属于[1..n] Example数组[3,1,2,5,7,8].回答:4, 6
我在另一篇类似的帖子中看到了这个解决方案,但我不明白最后一步:
- 找到数字的总和S = a1 + ... + an.
- 还可以找到平方和T =a1²+ ... +an².
- 你知道总和应该是S'= 1 + ... + n = n(n + 1)/ 2
- 你知道平方和应该是T'=1²+ ... +n²= n(n + 1)(2n + 1)/ 6.
- 现在建立以下方程组x + y = S'-S,x²+ y2 = T'-T.
- 通过写x²+ y2 =(x + y)²-2xy => xy =((S'-S)²-(T'-T))/ 2来求解.
- 现在这些数字仅仅是z中的二次曲线的根:z 2 - (S'-S)z +((S'-S)²-(T'-T))/ 2 = 0.
在z为未知的最后一步中设置二次方程的解释是什么？解决这个问题背后的直觉是什么？