<分区>
Possible Duplicate:
Quickest way to find missing number in an array of numbers
输入:未排序的数组 A[1,..,n]，其中包含 0,..,n 范围内除一个整数以外的所有整数
问题是在 O(n) 时间内确定缺失的整数。 A 的每个元素是 以二进制表示，唯一可用的操作是函数 bit(i, j)，它 返回 A[i] 的第 j 位的值并花费常数时间。
有什么想法吗？我认为某种分而治之的算法是合适的，但我想不出我到底应该做什么。提前致谢!
最佳答案
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) 获取数字很棘手，因此您必须单独提取位并将它们转换为实际数字以进行求和。
关于algorithm - 棘手的算法题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4040786/