Mar*_*yeh 63 java arrays algorithm
在求职面试中我被问到这个问题,我一直想知道正确的答案.
您有一个从0到n-1的数字数组,其中一个数字被删除,并替换为数组中已有的数字,该数字与该数字重复.我们如何在时间O(n)中检测到这个重复？
例如,1,2,3,4将成为一个数组1,2,2,4.
时间O(n 2)的简单解决方案是使用嵌套循环来查找每个元素的副本.
ric*_*ici 151
这可以在O(n)时间和O(1)空间上完成.
(该算法仅起作用,因为数字是已知范围内的连续整数):
在单次通过向量时,计算所有数字的总和,以及所有数字的平方和.
从中减去所有数字的总和N(N-1)/2.叫这个A.
从中减去平方和N(N-1)(2N-1)/6.除以此A.调用结果B.
删除(B + A)/2的号码是,它被替换的号码是(B - A)/2.
矢量是[0, 1, 1, 2, 3, 5]:
N = 6
矢量和为0 + 1 + 1 + 2 + 3 + 5 = 12.N(N-1)/ 2为15. A = 3.
平方和为0 + 1 + 1 + 4 + 9 + 25 = 40.N(N-1)(2N-1)/ 6为55.B =(55-40)/ A = 5.
删除的数字是(5 + 3)/ 2 = 4.
被替换的数字是(5 - 3)/ 2 = 1.
原始矢量的总和[0, ..., N-1]是N(N-1)/2.假设该值a已被删除并替换为b.现在修改后的矢量之和将是N(N-1)/2 + b - a.如果我们从中N(N-1)/2得到修改后的矢量的总和a - b.所以A = a - b.
类似地,原始矢量的平方和是N(N-1)(2N-1)/6.修改后的矢量的平方和是.从原始总和中减去修改后的矢量的平方和得到,与之相同.因此,如果我们将它除以(即),我们得到.N(N-1)(2N-1)/6 + b2 - a2a2 - b2(a+b)(a-b)a - bAB = a + b
现在B + A = a + b + a - b = 2a和B - A = a + b - (a - b) = 2b.
qPC*_*vir 34
我们有原始数组int A[N];创建第二个数组bool B[N],类型bool=false.迭代第一个数组并设置B[A[i]]=trueif是否为false,否则bing!
小智 31
您可以在O(N)时间内完成,而无需任何额外空间.以下是算法的工作原理:
以下列方式遍历数组:
对于遇到的每个元素,将其对应的索引值设置为负数.例如:如果找到[0] = 2.得到[2]并否定该值.
通过执行此操作,您可以将其标记为遇到.既然你知道你不能有负数,你也知道你是否是否定了它.
检查对应于该值的索引是否已标记为否定,如果是,则获取重复元素.例如:如果a [0] = 2,转到[2]并检查它是否为负数.
让我们说你有以下数组:
int a[] = {2,1,2,3,4};
在第一个元素后,您的数组将是:
int a[] = {2,1,-2,3,4};
在第二个元素后,您的数组将是:
int a[] = {2,-1,-2,3,4};
当你到达第三个元素时,你会转到[2]并看到它已经是负数.你得到了副本.
Evg*_*uev 11
扫描阵列3次:
A.将0到N-1 - >之间的所有数字进行异或B.现在A XOR B = X XOR D,其中X是删除的元素,D是重复的元素.A XOR B.将此位设置的所有数组元素XOR组合在一起 - > A1.将从0到N-1的所有数字进行异或运算,其中该位置位 - > B1.现在要么A1 XOR B1 = X或A1 XOR B1 = D.A1 XOR B1.如果找到,则这是重复元素.如果不是,则重复元素是A XOR B XOR A1 XOR B1.使用a HashSet来保存已经看过的所有数字.它在(摊销)O(1)时间运作,因此总计是O(N).
我建议使用BitSet.我们知道N对于数组索引来说足够小,所以BitSet的大小合理.
对于数组的每个元素,请检查与其值对应的位.如果已经设置,那就是重复.如果没有,请设置该位.
| 归档时间： |
|
| 查看次数： |
74659 次 |
| 最近记录： |