算法问题4
某数组A[1..n]含有所有从0到n的整数,但其中有一个整数不在数组中。通过利用一个辅助数组B[0..n]来记录A中出现的整数,很容易在O(n)时间内找出所缺的整数。但在这个问题中,我们却不能有一个单一操作来访问A中的一个完整整数,因为A中的元素是以二进制表示的。我们所能用的唯一操作就是“取A[i]的第j位”,这个操作所花的时间为常数。
证明:如果仅用此操作,仍能在O(n)时间内找出所缺的整数。
我可以在O(nlgn)的时间内找出来,但实在想不出O(n)的算法。
谢谢大家11