首页 > 代码库 > 40亿个有序不同的数的文件中找一个缺失的数
40亿个有序不同的数的文件中找一个缺失的数
编程珠玑第二题。。。
如果是用位图的话。。。
如果内存不够，那么就需要二分，注意思想就是先找到中间数mid，然后把文件以mid分为两个文件，肯定丢失的数在数目小的那个文件中，然后递归去那个小的文件中找就行了。
复杂度是o(2n) n+n/2+n/4+n/8+.....
看了别人写了一个代码：
int split(int* a, int* b, int*c, int alen, int bit){ int biter, citer, i; int v=0, re = 0, *t; while(bit--){ v = (1 << bit); for(i=biter=citer=0; i < alen; i++) { if(a[i] & (1<<bit)) { b[biter++] = a[i]; } else { c[citer++] = a[i]; } } if(biter <= citer) { re += v; t = a; a = b; b = t; alen = biter; } else { t = c; c = a; a = t; alen = citer; } } return re;}
40亿个有序不同的数的文件中找一个缺失的数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。