2012腾讯一面试题，高分邀请各路高手讨论
有2.5亿个整数存放在一个文件中，（已知内存容量没有此文件大）如何判断出这个文件中有多少个不相同的数。
[解决办法]
代码来了，用一位表示一个数……1为文件中存在此数，0则不存在……计算要表示2.5亿个数，要近30MB内存……
#include<stdio.h>
#include<stdlib.h>
void record(int **p,int k)
{
int i=k/32/5000;//p[i]
int j=(k-i*5000*32)/32;//p[i][j]
int m=k%32;//p[i][j]的第m位
int n=1;//用1代表数k，0则表示文件数据中没有数k
n<<=m;//确定位置，如12，第一个数p[0][0]的第12位为1,33则为第2个数p[0][1]的第33-32位为1,5001则p[1][1]的第1位为1
*(*(p+i)+j)
[解决办法]
=n;
}
void count_int(int *p,int *count)
{
register int i=0;//寄存器应该会更快……
register int j;
register int k;
while(i<5000)//遍历一指针数组中的5000个元素
{
j=0;
k=1;
while(j<32)//遍历每个整型元素中的32位
{
if(k&*p)//如果该位是1说明文件中有这个数，计数加1，0则无……
(*count)++;
k<<=1;//继续下一位
j++;
}
p++;//下一个元素……
i++;
}
}
void main()
{
FILE *fp;
register int i=0;
int k=0;//存放读出数据
int count=0;//记录不相同数的个数
int num=250000000;//要统计的整数个数
int memory_size=num/32;//要分配的内存
int *p[1563];//1566=memory_size/5000+1
char data_file[30];
for(;i<memory_size/5000+1;i++)
p[i]=calloc(5000,sizeof(int));//分配堆内存,并初始化，不能一下分配太大的一块，不然会出错，所以我把它分成1563块，每块5000个整型元素
printf("\n请输入存放数据的文件路径：");
gets(data_file);
if((fp=fopen(data_file,"rb"))==NULL)//打开数据文件
{
printf("\n文件打开错误!");
exit(0);
}
else
{
while(!feof(fp))//如果未到文件尾则继续
{
fscanf(fp,"%d",&k);//读出一个整型数据
record(p,k);//把内存p中第k位（bit位）变1
}
}
for(i=0;i<1563;i++) //遍历指针数组中的所有元素……
count_int(p[i],&count);
printf("\n共有 %d 个不相同的数!\n",count);
}
#include<stdio.h>
#include<stdlib.h>
void record(int **p,int k) //记录数据文件中读出的数……
{
int i=k/32/5000; //p[i]
int j=(k-i*5000*32)/32; //p[i][j]
int m=k%32; //p[i][j]的第m位
int n=1; //用1代表数k，0则表示文件数据中没有数k
n<<=m; //确定位置，如12，第一个数p[0][0]的第12位为1,33则为第2个数p[0][1]的第33-32位为1,5001则p[1][0]的第1位为1
*(*(p+i)+j)
[解决办法]
=n;
}
void count_int(int *p,int *count) //统计读出来的不同数的个数……
{
register int i=0; //寄存器应该会更快……
register int j;
register int k;
while(i<5000) //遍历一指针数组中的5000个元素
{
j=0;
k=1;
while(j<32) //遍历每个整型元素中的32位
{
if(k&*p) //如果该位是1说明文件中有这个数，计数加1，0则无……
(*count)++;
k<<=1; //继续下一位
j++;
}
p++; //下一个元素……
i++;
}
}
void main()
{
FILE *fp;
register int i=0;
int k=0; //存放读出数据
int count=0; //记录不相同数的个数
unsigned int num=4294967295; //要统计的整数个数
int memory_size=num/32; //要分配的内存
int *p[26844]; //26844=memory_size/5000+1
char data_file[30]; //要打开的数据文件名
for(;i<memory_size/5000+1;i++)
p[i]=calloc(5000,sizeof(int)); //分配堆内存,并初始化，不能一下分配太大的一块，不然会出错，所以我把它分成26844块，每块5000个整型元素
printf("\n请输入存放数据的文件路径：");
gets(data_file);
if((fp=fopen(data_file,"rb"))==NULL) //打开数据文件
{
printf("\n文件打开错误!");
exit(0);
}
else
{
while(!feof(fp)) //如果未到文件尾则继续
{
fscanf(fp,"%d",&k); //读出一个整型数据
record(p,k); //把内存p中第k位（bit位）变1
}
}
for(i=0;i<26844;i++) //遍历指针数组中的所有元素……
count_int(p[i],&count);
printf("\n共有 %d 个不相同的数!\n",count);
}
