查找数组中缺少的数字

Question

数组a[]包含从0到N的所有整数,除了一个.但是,您无法通过单个操作访问元素.相反,你可以调用get(i, k)哪个返回第k位,a[i]或者你可以调用swap(i, j)哪个交换第i个和第j个元素a[].设计O(N)算法以找到缺失的整数.(为简单起见,假设N是2的幂.)

Answer 1

如果N是2的幂,则可以O(N)使用除法和征服来完成.

请注意,logN数字中有位.现在,使用此信息 - 您可以使用基于分区的选择算法和基数排序的组合.

1. 迭代第一位的数字,并将数组分成两半 - 前半部分将此位设为0,另一半将其设为1.(使用swap()for分区数组).
2. 请注意,一半有ceil(N/2)元素,另一半有floor(N/2)元素.
3. 对较小的数组重复此过程,直到找到缺少的数字.

这种方法的复杂性将是N + N/2 + N/4 + ... + 1 < 2N如此O(n)