【答案解析】在海量数据中查找出重复出现的元素或者去除重复出现的元素也是常考的问题。针对此类问题，一般可以通过位图法实现。例如，已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
本题最好的解决方法是通过使用位图法来实现。8位整数可以表示的最大十进制数值为99999999。如果每个数字对应于位图中1bit(位)，那么存储8位整数大约需要99MB。因为1B=8bit，所以99Mbit折合成内存为99/8=7.375MB的内存，即可以只用7.375MB的内存表示所有的8位数电话号码的内容。
程序示例如下：
#include＜iostream＞
#include＜time.h＞
using namespace std;
#define BITWORD 32
#define ARRNUM 100
int mmin=10000000;
int mmax=99999999;
int N=(mmax-mmin+1);
#define BITS PER WORD 32
#define WORD_OFFSET(b)((b)/BITS_PER_WORD)
#define BIT_OFFSET(b)((b)%BITS_PER_WORD)
void SetBit(int *words, int n)
{
n-=mmin;
words[WORD_OFFSET(n)]|=(1＜＜BIT_OFFSET(n));
}
void ClearBit(int *words, int n)
{
words[WORD_OFFSET(n)]&=～(1＜ BIT_OFFSET(n));
}
int GetBit(int *words,int n)
{
int bit=words[WORD_OFFSET(n)]&(1＜＜BIT_OFFSET(n));
return bit!=0;
}
int main()
{
int i;
int j;
int arr[ARRNUM];
int* words=new int[1 +N/BITS_PER_WORD];
if(words==NULL)
tout＜＜"new error/n"＜＜endl;
exit(0);
int count=0;
for(i=0;i＜N;i++)
{
ClearBit(words,i);
}
srand((unsigned)time(NULL));
printf("数组,:%d/n"ARRNUM);
for(j=0; j＜ARRNUM;j++)
{
arr[j]=rand()%N;
arr[j]+=mmin;
printf("%d/t",arr[j]);
}
for(j=0;j＜ARRNUM;j++)
{
SetBit(words,arr[j]);
}
printf("排序后a为:/n");
for (i = 0; i ＜ N; i++)
{
if (GetBit(words,i))
{
printf("%d/t",i+mmin);
count++;
}
}
printf("总个数为:%d/n",count);
delete[] words;
words=NULL;
return 0;
}
上例中，采用时间作为种子，产生了100个随机数，对这100个数进行位图法排序，进而找出其中重复的数据。与此问题相似的面试笔试题如下：
1)10亿个正整数，只有1个数重复出现过，要求在O(n)的时间里找出这个数。
2)给定a、b两个文件，各存放50亿个ur1，每个ur1各占用64B，要求在O(n)的时间里找出a、b文件共同的ur1。
3)给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中?