可能重复:
在数字数组中查找缺失数字的最快方法
输入:未排序的数组 A[1,..,n] 包含范围 0,..,n 中除一个整数之外的所有整数
问题是在 O(n) 时间内确定丢失的整数。A 的每个元素都用二进制表示,唯一可用的操作是函数 bit(i, j),它返回 A[i] 的第 j 位的值,并花费常数时间。
有任何想法吗?我认为某种分而治之的算法是合适的,但我想不出我到底应该做什么。提前致谢!
可能重复:
在数字数组中查找缺失数字的最快方法
输入:未排序的数组 A[1,..,n] 包含范围 0,..,n 中除一个整数之外的所有整数
问题是在 O(n) 时间内确定丢失的整数。A 的每个元素都用二进制表示,唯一可用的操作是函数 bit(i, j),它返回 A[i] 的第 j 位的值,并花费常数时间。
有任何想法吗?我认为某种分而治之的算法是合适的,但我想不出我到底应该做什么。提前致谢!
1
这是一个数学性质,即和n
where之间的数字之和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
因此,通过扩展,是thru的数字之和,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)
很棘手,因此您必须单独提取这些位并将它们转换为实际数字以进行求和。
您可以使用 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
}
这是一个棘手的问题,因为使用 bit 方法只需要为每个数字循环每个位,这意味着它将自动变为 O(n*j),其中 j 是表示 n 的位数。
我认为 paxdiablo 得到了它,假设您被允许使用不使用 bit 方法的解决方案。