算法导论思考题 找出所缺的数字

此题出自《算法导论》第4章递归式思考题4-2。

【题目说明】

某数组A[1...n]含有所有从0到n的整数，但其中有一个整数不在数组中，现在要找出这个不在数组中的整数。

因为A中的元素用二进制表示的，所以我们能用的唯一操作就是“取A[i]的第j位”，这个操作花费常数时间。

证明：如果访问数A中的信息的唯一方式是这种单一的位操作，仍能在O(N)时间内找出所缺的整数。

【分析】

如果一次能取出完整的A[i]，则可以通过异或或者求和的方法找出。

然而一次只能取某数的一个位，故取完所有位即可获得该数，时间复杂度O(nlogn)。

其实，我们可以通过以某种取法，避免对每个数字的所有位都进行该操作来提高效率。

对于数组A[1...n]，其数据范围为[0,n]，取n的最高为1的位，记为maxBit位，则有(1<<maxBit) <= n < ( 1 << (maxBit+1) )。

然后遍历A中的元素，获得数组中maxBit位为1的个数，记为cnt，如果cnt == ( n - (1<<maxBit) + 1 )，则说明maxBit位中的元素都有，即缺失的数字该位为0，否则为1，从而将问题转化为一个规模更小的子问题。

其时间复杂度：T(N) = T(N/2) + O(N).

n^(log2(1)+1) = n ， 故T(N) = O(N).

【完整代码】

//karsbin 2012.11.13/* *1.封装一个操作，对于某个数组，只能取第i个数的第k位，数组从1开始 *2.O(N)实现查找所缺数字 */#include <stdio.h>#include <stdlib.h>#include <time.h>#include <string.h>const int maxn = 1024 ;int array[maxn] ;bool vis[maxn] ;//返回j个第i个位，从低到高[0,31]，返回值为1或者0int getIthOfJ(int i,int j){return ( j & ( 1 << i ) ) > 0 ? 1 : 0 ;}//唯一可以访问array的操作,取第array[i]的第k位int pick(int i, int k){return getIthOfJ(k, array[i]);}//创建一个数组，array[1]到array[n]包含有[0,n]中除了一个数字的所有其他数字void buildArray(int n){if( n >= maxn - 1 ) {n = maxn - 2 ;}srand(time(NULL));int i ;for( i = 1 ; i <= n + 1 ; i++) {array[i] = i - 1 ;}int missingNumber = rand() % ( n + 1 ) ;printf("构造了一个数据范围为0到%d的数组，缺失的数字为%d\n",n,missingNumber);//移除一个随机数for( i = missingNumber + 1 ; i <= n ; i++) {array[i] = array[i+1] ;}printf("构造如下数组：\n");for ( i = 1 ; i <= n ; i++){printf("%d ",array[i]);}puts("");}//返回缺失的数字int getTheMissingNumber(int n){//边界if ( n == 0 ){return 0 ;}int i , j , maxBit , cnt ;int ans = 0 ;for( maxBit = 31 ; maxBit >= 0 ; maxBit--) {if( getIthOfJ(maxBit, n) == 1 ){break ;}}memset(vis,0,sizeof(bool)*(n+1));for ( i = 1 , cnt = 0 ; i <= n ; i++){vis[array[i]] = 1 ;if ( getIthOfJ(maxBit, array[i]) == 1 ){//cnt记录array[i]中最高位maxbit为1的个数cnt++;}}if ( cnt == (n-(1<<maxBit)+1) ){//结果的最高位为0，拷贝最高位为0的数组进arrayfor ( i = j = 0 ; i < (1<<maxBit) ; i++) if( vis[i] == 1 ){array[++j] = i ;}ans = getTheMissingNumber(j);}else{//结果的最高位为1，拷贝最高位为0的数组进arrayfor ( i = ( 1 << maxBit ) , j = 0 ; i <= n ; i++) if( vis[i] == 1 ){array[++j] = i ^ ( 1 << maxBit ) ;}ans = (1 << maxBit) | getTheMissingNumber(j) ;}return ans ;}int main(){int n ;while (~scanf("%d",&n)){buildArray(n);printf("所缺失的数字为：%d\n",getTheMissingNumber(n));}}