赞
踩
具体题目要求:给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。
思路:(1)用一个无符号整数表示一个无符号整数时,40亿个无符号整数要全部加载到内存,大概需要16G的内存。
(2)如果用一个字节表示一个数,大概需要4G内存。
(3)如果用一位表示一个数是否存在,大概需要500MB。
(4)假设我们只有250MB内存时,需要把文件切分,分开加载。
这次我用的方法是位图来判断这个数是否存在。
位图:位图是一个数组的每一个数据的每一个二进制位表示一个数据,1代表存在,0代表不存在。
- <span style="font-size:24px;">#include<vector>
- class BitSet
- {
- public:
- BitSet(const size_t& range)
- {
- _bitset.resize(range>>5+1); //>>5相当于除以32,得到需要多大内存空间
- //(range>>3+1) range为char
- }
- //0变为1
- void Set(const size_t& x)
- {
- size_t index=x>>5; //得到x在第几个size_t
- size_t num=x%32; //在得到x在第几位
- _bitset[index]|=(1<<num); //0或1为1
- }
- //1变为0
- void ReSet(const size_t& x)
- {
- size_t index=x>>5; //得到x在第几个size_t
- size_t num=x%32; //在得到x在第几位
- _bitset[index]&=(~(1<<num)); //0与1为0
- }
- //判断是0,返回false,1返回true
- bool Test(const size_t& x)
- {
- size_t index=x>>5; //得到x在第几个size_t
- size_t num=x%32; //在得到x在第几位
- return _bitset[index]&(1<<num);//不为0,则返回true
- }
- private:
- vector<size_t> _bitset;
- };</span>
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。