棘手的算法问题

Question

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

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

问题是在 O(n) 时间内确定丢失的整数。 A 的每个元素是 以二进制表示，唯一可用的操作是函数 bit(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
}

Answer 3

这是一个棘手的问题，因为使用位方法只需要循环每个数字的每一位，这意味着它会自动变成 O(n*j)，其中 j 是代表 n 的位数。

我认为 paxdiablo 已经明白了，假设您被允许使用不使用位方法的解决方案。