1、1. 给 40 亿个不重复的 unsigned int 的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那 40 亿个数当中A. 申请 512M 的内存 一个 bit 位代表一个 unsigned int 值 读入 40 亿个数，设置相应的 bit 位 读入要查询的数，查看相应 bit 位是否为 1，为 1 表示存在，为 0 表示不存在B. 1.unsigned int 32 位有 40 亿个的，这是事实 2.确实是用位图做的，512M 内存-C. 使用位图法判断整形数组是否存在重复 判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循
2、环法就不可取了。 位图法比较适合于这种情况，它的做法是按照集合中最大元素 max 创建一个长度为 max+1 的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上 1，如遇到 5 就给新数组的第六个元素置 1，这样下次再遇到 5 想置位时发现新数组的第六个元素已经是 1 了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为 2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。-D. 我的解法，看看还能不能优化了。 #include #include #define BITPERINT
3、 32 /每个 int 型字节数 #define BITPERCHAR 8 /每个 char 型字节数 #define N 4000000000 /40 亿个数 #define SIZE N/BITPERINT #define MASK 0x80 /1000000 掩码 /犹豫 40 亿个数会超出栈空间，所以在堆上分配动态数组。 typedef struct BitList unsigned char *base; int intLength; BitList,*P_BitList; /初始化线性顺序表，总位数为 intSize*BITPERCHAR int InitBitList(BitLi
4、st if(BL.base = NULL) printf(“n Out of memomry !n“); exit(0); /内存初始化为 0 for(int i = 0;i intBitIndex); return 1; /清除标志位，将堆中内存的第 intIndex 位设置为 0(关) int ClrList(BitList int intBitIndex = intIndex%BITPERCHAR; BL.baseintListIndex = BL.baseintListIndex(MASKintBitIndex); return 1; /获取堆中内存的第 intIndex 位的值（0
5、或 1） int GetList(BitList int intBitIndex = intIndex%BITPERCHAR; return ( BL.baseintListIndex int main() BitList bl; InitBitList(bl,SIZE); for(int i =0;i 5 = bx5char map2char=1,2,3,4,5,6,7,8,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y;void getbit( unsigned e, char *s, int offset )int i=17;while(
6、i=0 )s18*offset+i=(ei)-i; int main(int argc, char *argv) srand(GetTickCount();char bit90, S90;for( int i=0; i 60) for (int j = 0; j (55 - j * 5) Data14 = Data12;Data12 = CONST_OTHER_CHARS0;Data15 = Data5;Data5 = CONST_OTHER_CHARS1;Data16 = Data9;Data9 = CONST_OTHER_CHARS2;Data17 = Data7;Data7 = CONS
7、T_OTHER_CHARS3;unsigned long j;WriteFile( hFile,Data,20,if (Counter = 1000000) break;CloseHandle(hFile);QueryPerformanceCounter(LARGE_INTEGER u64_pfmc_freq, timer;QueryPerformanceFrequency(timer.QuadPart = (u64_pfmc_end.QuadPart - u64_pfmc_start.QuadPart) * 1000 / u64_pfmc_freq.QuadPart;char msg100;
8、_ui64toa(timer.QuadPart,msg,10);MessageBox(GetActiveWindow(),msg,“消耗时间(毫秒)“,MB_OK);/穷举0-9a-z0-9a-z给一个链表 m 要计算 36*36*给链表赋值的时间次 a10 对 a0-9 每个数组都随机给这个链表的 n/10 项（也可以项数不等） ，链表被复制的项删除 36*36*链表删除的时间 之类， 对 00000001-999999999 分别按位在该位数的区间内随机取值，这个数必然不重复。 要计算比 10 亿*8*n/10 多一些的次数。 这个算法应该不算慢了吧？ 知道算法想硬碰一个数的概率是(10/(36*36)的 10 次幂 安全性可能比完全随机的数要差，但我感觉在平常应该足够了吧？似乎也挺低了。 而且如果顺序保存的话查找也会省不少时间。/
