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);
}

[解决办法]

引用:

代码来了，用一位表示一个数……1为文件中存在此数，0则不存在……计算要表示2.5亿个数，要近30MB内存……


C/C++ code
#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……

2.5亿个位不能表示完整的整型，最大的整数只能是2.5亿，楼上说的对，要完整的把整型的全部范围表示出来，经计算是得512M的内存……

改过后的，在我机子上要等上个十秒左右才能遍历完2^32个位，如果读的数更据多，那就要更久了……

#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);  
}  

[解决办法]

引用:

引用:
引用:
2个2.5亿bits的bitmap。

第一个bitmap某一位为1表示此数出现过。
第二个bitmap某一位为1表示此数重复出现过。


扫一遍文件即可获得答案，找出那些第一个bitmap为1，第二个bitmap位0的。


额，说的有点问题.

准确的说应该是2^size……

其实效率可以很高的,

1,扫描文件读取2.5亿个整数k,对于每一个整数,查bitmap1的k位,如果为0则设为1,如果为1,则设bitmap2的k位为1.

2,对于bitmap1,bitmap2,由于bitmap实现起来我们都是用数组实现的,char bitmap1[2.5亿/8]; char bitmap2[2.5亿/8]; 所以统计的时候,我们需要统计bitmap1为1而bitmap2为0的个数,只要将两个数组逐字节异或即可. 之后利用求一个整数里有几个1的算法,对每个char做这个算法,累加起来就是不重复数字的个数.

支持一下，基本方法是对的。将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map。