我有一段时间有一个有趣的面试经历.问题开始很简单:
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到N的整数值的N个元素的只读数组(某些整数值可以出现多次!).和固定大小的存储区(10,100,1000等 - 不依赖于N).
如何在O(n)中判断数组是否代表一个排列？
-什么我实现了迄今(答案证明,这是不是好): -
我知道如果条件(2)为真,我可能会有一个排列.我想知道是否有办法证明条件(2)足以判断我是否有排列.到目前为止,我还没想出来......
通过时间复杂度，我们将算法的运行时间理解为输入大小（表示内存中实例所需的位数）的函数。那么，关于这一观察，我们如何定义空间的复杂性呢？它显然与实例的大小无关...