我有一段时间有一个有趣的面试经历.问题开始很简单:
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中定义.
所以这里的问题很简单:
在长度为n的序列中,其中n = 2k + 3,即有k个唯一数字出现两次,并且三个数字仅出现一次.
问题是:如何找到仅出现一次的三个唯一数字？
例如,在顺序1 1 2 6 3 6 5 7 7中,三个唯一数字是2 3 5.
注意:3 <= n <1e6,数字范围为1到2e9
内存限制:1000KB,这意味着我们无法存储整个序列.
方法我试过(内存限制超过)？
我初始化一个树,当读入一个数字时,我尝试将其从树中删除,如果remove返回false(未找到),我将它添加到树中.最后,树有三个数字.它工作,但内存限制超过.
我知道如何使用位操作找到一个或两个这样的数字.所以我想知道是否
我们可以找到三个使用相同的方法(或一些类似的方法)？
找到一个/两个数字的方法只出现一次:
如果只有一个数字出现一次,我们可以对序列应用XOR来找到它.
如果有两个,我们可以先对序列应用XOR,然后将序列分成2个部分,结果为1,然后再将XOR应用于2个部分,我们将找到答案.
假设你有一个大小为n的数组A [1..n],它包含集合{1..n}中的元素.但是,缺少两个元素(并且可能重复了两个数组元素).找到缺少的元素.
例如,如果n = 5,A可以是A [5] = {1,2,1,3,2}; 所以缺少的元素是{4,5}
我使用的方法是:
int flag[n] = {0};
int i;
for(i = 0; i < n; i++) {
flag[A[i]-1] = 1;
}
for(i = 0; i < n; i++) {
if(!flag[i]) {
printf("missing: %d", (i+1));
}
空间复杂性来自O(n).我觉得这是一个非常儿童和低效的代码.那么请你提供一个更好的空间和时间复杂度的更好的算法.
可能重复:
简单的面试问题变得更难:给定数字1..100,找到丢失的数字
在线性时间和恒定空间中找到数组中缺失和重复的元素
我在一个论坛上看到了一个有趣的问题.
你有100个元素,从1到100,但是由于错误,其中一个数字重复另一个重复自己.例如1,99,3,...,99,100数组不是排序格式,如何找到重复数？
我知道哈希可以做O(n)时间和O(n)空间,我需要O(1)空间.