algorithm - 通过 CLRS 练习了解运行时间分析

Question

这是我正在寻找答案的问题:

数组 A[1...n] 包含从 0 到 n 除了 1 之外的所有整数。很容易确定丢失的O(n) 时间内的整数通过使用辅助数组 B[0...n] 来记录哪些数字出现在 A 中。在这个然而，问题是，我们无法通过一次操作访问 A 中的整个整数。 A 的元素是以二进制表示，我们可以用来访问它们的唯一操作是“获取 A[i] 的第 j 位”，它需要恒定的时间。表明如果我们只使用这个操作，我们仍然可以在 O(n) 时间内确定丢失的整数。

我想到了这种方法:如果我没有上面的获取限制，我会把所有的数字都拿来一起做异或运算。然后将结果与 1..n 中的所有数字进行异或。结果就是我的答案。类似地，在这个问题中，我可以重复对数组中所有元素的 log(n+1) 位距离处的不同数字的位进行异或，然后将它们与元素 1...n 进行异或，但复杂度为在我看来是 O(nlogn)。

如何实现 O(n) 的复杂度？谢谢

Answer 1

您可以使用 radix sort 的变体:

根据 MSb(最高有效位)对数字进行排序
你得到两个大小为n/2，n/2-1的列表。您可以“删除”包含 n/2 个元素的列表 - 缺少的数字不存在。

对第二个 MSb 重复，依此类推。

最后，您选择的“路径”(每个位列表较小的位)将代表缺失的数字。

复杂度是 O(n + n/2 + ... + 2 + 1) , 自 n + n/2 + .. + 1 < 2n - 这是 O(n)

---

为简单起见，此答案假定 n=2^k对于某个整数 k (稍后可以通过对 MSb 执行“特殊”处理来取消这种放松)。