【转】
问题： 某数组A[1..n]含有所有从0..n的所有整数，但其中有一个整数不在数组中，通过利用一个辅助数组B[0..n]来记录A中出现的整数，很容易在O(n)时间内找出所缺的整数。但在这个问题中，我们却不能由一个单一操作来访问A中的一个完整整数，因为A中元素是以二进制表示的。我们所能用的唯一操作就是“取A[i]的第j位”这个操作所花时间为常数。 问题： 某数组A[1..n]含有所有从0..n的所有整数，但其中有一个整数
阅读背景：
算法导论-4-2 找出所缺的整数
来源：互联网
分享到：
