棘手的算法问题

Question

可能重复:
在数组中查找缺失数字的最快方法

输入:未排序的数组A [1,..,n],其中包含0,...,n范围内的除整数之外的所有整数

问题是在O(n)时间内确定缺失的整数.A的每个元素以二进制表示,唯一可用的操作是函数位(i,j),它返回A [i]的第j位的值并占用恒定时间.

有任何想法吗？我认为某种分而治之的算法是正确的,但我想不出我应该做什么.提前致谢!

Answer 1

这是一个数学属性,号码之间的总和1,并n在那里n为n(n+1)/2.你可以看到这个10:

  1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
= (1+10) + (2+9) + (3+8) +(4+7) + (5+6)
= 11 + 11 + 11 + 11 + 11
= 55

因此,推而广之,是数字从和0通n,因为你只需添加0到它.所以你要做的就是将所有数字相加并保持计数,然后使用该公式计算出缺失的数字.

所以,像:

count = 0
sum = 0
foreach num in list:
    sum = sum + num
    count = count + 1
missing = count * (count+1) / 2 - sum

获取数字bit(i,j)非常棘手,因此您必须单独提取这些位并将它们转换为实际数字以进行求和.

Answer 2

你可以使用XOR运算符比添加更快.由于您可以访问每个位,因此您将在此处执行按位异或.这里使用的原则是(A XOR B XOR A)= B.

例如:(1 XOR 2 XOR 3)XOR(1 XOR 2)= 3

for i=0 to n
{
Total=Total XOR i
}

foreach element in A
{
Total=Total XOR element
}