寻找数组中缺少的整数(Find the missing integer)
数组a中含有N个元素,其元素属于[0,N]之间,且不存在重复的元素,请你找出数组中缺失的元素(因为[0,N]之间有N+1个元素,而数组只能存储N个元素,所以必然缺少一个元素)。其中对数组的操作满足下列的条件:不能在常数时间内读取数组中的元素,但是可以读取数组中元素的某一个bit值,能够在常数时间内交换数组的两个元素的位置。请设计一种算法使其能够在线性时间内找出数组中缺失的元素。(N=2^k)
An array a[] contains all of the integers from 0 to N, except 1. However, you cannot access an element with a single operation. Instead, you can call get(i, k) which returns the kth bit of a[i] or you can call swap(i, j) which swaps the ith and jth elements of a[]. Design an O(N) algorithm to find the missing integer. For simplicity, assume N is a power of 2
算法设计:有题设可知,[0,N]之间奇数和偶数个数之差等于1,如果缺失偶数,则奇数和偶数的数目相等,反之缺失奇数。如何判断元素的奇偶呢?题设给出只能在常数时间内访问数组元素的某个bit值,所以只需看元素的最后一个bit为0还是1即可,这样通过一次扫描数组可以排除n/2个元素。利用此法(判断0,1个数的多少)我们就可以找出缺失的元素。重复上述操作即可。
算法性能分析:
第一次扫面元素判断奇偶,需要循环n次,从而排除n/2个元素,因此第二次循环需要循环n/2次,一次类推,总共的循环次数为T
T=n+n/2+n/4+n/8+……+1=O(n),为此达到了题目的要求。
算法实现:
<span style="font-size:10px;">void swap(int* a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } int get(int* a, int i, int k) { int res = a[i]>>k & 1; return res; } int Find_the_missing_integer(int* a, int low, int high) { int res = 0; int power = 1; int count0 = 0; int count1 = 0; int n = high-low+1; int pointer0 = 0; int i=0; while(n>0) { for(int j=low; j<=high;j++) { if(get(a,j,i) == 0) { count0++; swap(a,j,pointer0); pointer0++; } else { count1++; } } if(count0>count1) { res = res + power*1; low = pointer0; n = count1; } else { res = res + power*0; high = pointer0 - 1; pointer0 = low; n = count0; } power = power*2; count0 = 0; count1 = 0; i++; } return res; }</span>
算法解释:find_the_missing_intger,函数中利用pointer记录最后一个元素的0还是1的分界点,然后每次都循环扫面满足我们要求的那一部分元素,直到最终没有元素位置。
测试代码:
#include <iostream> using namespace std; void swap(int* a, int i, int j); int get(int* a, int i, int k); int Find_the_missing_integer(int* a, int low, int high); void main() { int a[]={1,2,3,4,5,6,7,0}; cout<<Find_the_missing_integer(a,0,7); }
如有不清楚的地方欢迎讨论。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。