这是我正在寻找答案的问题:
数组 A[1...n] 包含从 0 到 n 的所有整数,除了一个。通过使用辅助数组 B[0...n] 记录哪些数字出现在 A 中,很容易在 O(n) 时间内确定丢失的整数。然而,在这个问题中,我们不能访问 A 中的整个整数一次操作。A 的元素以二进制表示,我们可以用来访问它们的唯一操作是“获取 A[i] 的第 j 位”,这需要恒定的时间。证明如果我们只使用这个操作,我们仍然可以在 O(n) 时间内确定丢失的整数。
我想到了这种方法:如果我没有上述获取限制,我会取所有数字并将它们一起进行 XOR。然后将结果与 1..n 中的所有数字进行异或运算。这将是我的答案。在这个问题中,类似地,我可以对数组中的所有元素在 log(n+1) 位的距离上重复异或不同数字的位,然后将它们与元素 1...n 异或,但复杂性出现在我看来是 O(nlogn)。
如何实现 O(n) 复杂度?谢谢