Massive Algorithms: 算法导论 4-2 - newdye的专栏 - 博客频道

算法导论 4-2 - newdye的专栏 - 博客频道 - CSDN.NET

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

2 分析与解答

显然要运用递归思想，如果n为基数，那么0~n有(n+1)/2个奇数和(n+1)/2个偶数；同理当n为偶数时，有n/2+1个偶数，和n/2个奇数。
所以，假设如果A[1..n]中偶数个数不足，那么就要在A[1..n]的偶数元素中查找所缺整数，那么每次查找的数量就减半；将偶数元素左移一位得到的数组同样具有上述特性。反复应用此方法，直到两种情况：

奇数个数为0说明缺的位为1；
只剩一位时，不存在的那位就是所缺的；

这样就能得到基本递归算法，可以得到递归式T(n)=T(n/2)+D(n)+C(n)；
在来看D(n)显然分解需要扫描整个A[1..n]，所以D(n)=O(n)；
对于C(n)，算法应该不需合并，推测其时间复杂度为常数，即C(n)=O(1)；
所以，若算法满足上述条件，递归式为T(n)为T(n)=T(n/2)+O(n)，根据主定理可得，此递归式解为T(n)=O(n)。
证明：可以找到满足上述条件的算法。
设取A[i]的第j位操作为value(A[i],j)；
因为整数在A中以二进制形式存储，那么value(A[i], 0)就代表A中元素的奇偶性；
而value(A[i], 1)就代表A中元素左移一位的奇偶性，以此类推，直至奇数个数为0或只剩1位。

http://www.cnblogs.com/longdouhzt/archive/2011/07/15/2107742.html

基本方法就是用二分法：

1, 遍历整数0到n的第一位，分成两个数组：P1[1] 和P0[1]，分别代表第一位是1，0的数，并记录第一位是1的个数CountN，代价为O(n)
2, 遍历数组A[1...n]的第一位, 分成两个组：Q1[1]和Q0[1]，分别代表第一位是1，0的数，并记录1的个数CountA，代价为O(n)
3, 比较CountN和CountA的值，结果可能有两种情况CountN = CountA，或者CountN = CountA + 1，前者表明所缺数的第一位为0，后者为1，代价为O(1)
4, 通过3的结果，随后我们可以在P1[1]和Q1[1]（CountN>CountA，即缺少第一位为1的数）或者 P0[1]和Q0[1](CountN=CountA，即缺少第一位为0的数)中的第2位中重复步骤1，2中的操作，记录数组P1[2]、P0[2]和 CountN'及Q1[2]、Q0[2]和CountA'。代价为O(n/2)和O(n/2), 经过比较后可得到所缺数第二位是0还是1，决定接下来比较P1[2]和Q1[2] 或者 P0[2]和Q0[2]，代价O(1)
5, 不断重复Ceiling(lg(n))次，最后即可找到所缺数总代价为2* (O(n) + O(n/2) + ... +O(n/pow(2, k))) + ... + O(1)) = 2* O(2n) = 4*O(n) = O(n)

当然这里忽略了一个问题，如果A中缺了一个，这应该是n-1个数，则多出来的那个数是什么呢，如果和其他数有重复，上面的方法就无效了，情况变得相当复杂。因此上面的只适用于多出的一个数为0，或者干脆就只有n-1个数。

比较弱的方法：1到n所有数字加起来的和减去 A[1]到A[n]的和

比较犀利的方法：凑m，m=4k-1,并且是4k-1>=n的最大整数(比如n=7，则m=7；n=16，则m=19；n=21，m=23以此类推)
那么只需要A[1]^A[2]^……^A[n-1]^A[n]^{A[m-2]^A[m-1]^A[m]}，即可

原因：从4的整数倍开始，连续4个数字异或，结果为(例如4^5^6^7的结果是0；204^205^206 = 207；8^10^11=9)
所以0^1^2^……^m的结果为0，却哪个数字，则A[1]^A[2]^……^A[n-1]^A[n]^{A[m-2]^A[m-1]^A[m]}的结果就是所缺的数字

def loss_digital(A, n, i):
    if n == 1:
        if (A[0] >> i-1) == 0:
            return 1
        else:
            return 0

    #division O(n)
    array_odds = [x for x in A if (x >> (i-1)) & 0b1 == 1]
    array_evens = [x for x in A if (x >> (i-1)) & 0b1 == 0]

    #conque
    odds_actual = len(array_odds)
    if odds_actual == 0:
        return 1
    else:
        if n%2 == 0:
            odds_full = n/2
        else:
            odds_full = (n+1)/2
        if odds_actual == odds_full:
            return 2*loss_digital(array_evens, n-odds_full, i+1)
        else:
            return 1 + 2*loss_digital(array_odds, odds_actual, i+1)

http://blog.csdn.net/bin314/article/details/8179676

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

对于数组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).

const int maxn = 1024 ;
int array[maxn] ;
bool vis[maxn] ;

//返回j个第i个位，从低到高[0,31]，返回值为1或者0
int 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的数组进array
  for ( i = j = 0 ; i < (1<<maxBit) ; i++) if( vis[i] == 1 )
  {
   array[++j] = i ;
  }
  ans = getTheMissingNumber(j);
 }
 else
 {
  //结果的最高位为1，拷贝最高位为0的数组进array
  for ( 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));
 }
}

题目：数组A中包含n-1个[0,n-1]内的不同整数，n个数中只有一个数不在所给的数组中。设计一个找到这个数的O(n)时间的算法。除了数组A自身以外，只能利用O(1)的额外空间。

解法二：异或运算。异或是个非常神奇的运算。设所缺的整数为k，[0,n-1]区间中所有n个数的异或结果为s(n)，异或运算满足交换率和结合率，所以s(n)可以被看作[0,n-1]中去掉k外的另外n-1个数的异或结果s(n-1)和k的异或。也即：s(n)=s(n-1)^k，我们给等式两边同时异或s(n-1)，等式变成了：s(n-1)^s(n)=s(n-1)^s(n-1)^k=k。而且，很明显s(n-1)其实就是数组A中所有元素的异或。所以，解法二就是：求出[0,n-1]内所有整数的异或结果s，再求出数组A中所有元素的异或结果t，所缺的整数就是s异或t。

解法三：因为A自身也有n-1个位置。可以把A作为一个散列表，这样做虽然能够得到结果，但是破坏了数组A。

至于《算法导论》思考题4-2的解法，在《算法艺术与信息学竞赛》上有解答。思路简述：自然数顺序的二进制表示最低位总是0和1交替出现，所以，首先读取数组A中所有元素的最低二进制位，如果得到的0和1的个数一样多，则说明所缺整数的最低二进制位为0，否则，哪个少，所缺整数的最低二进制位就是哪个。比如，我们得到所缺整数的最低二进制位为0，那么，说明数组A中最低二进制位为1的那些整数已经与此题无干，只需要在那些最低位为0的整数中找所缺整数。所以，时间复杂度是：T(n)=T(n/2)+n，计算：

对n的上取整或下取整不影响时间复杂度。即T(n)=O(n)。

Read full article from 算法导论 4-2 - newdye的专栏 - 博客频道 - CSDN.NET

算法导论 4-2 - newdye的专栏 - 博客频道 - CSDN.NET

2 分析与解答

Labels

Popular Posts