首页 > 代码库 > 开篇——给磁盘文件排序

开篇——给磁盘文件排序

问题描述:

输入:是一个包含n个正整数的文件,每个数都小于n,n<10^7如果在输入文件中出现任何重复整数就是致命错误

输出:按升序排列的输入的整数列表

约束:最多有1MB 的内存可用,有充足的磁盘存储空间,运行时间最多几分钟,10秒即可不比优化

题解:

内存只有1MB,即最多能存1024*1024*8位二进制数,一个int型占32字节,每个字节是8位

采用位图存储集合,每个二进制位表示该位置所表示的数字存在与否,采用位运算提高程序运行速度

代码如下:

#include<iostream>
#include<string.h>
using namespace std;
const int N=100;
const int MAXN=0x1F; // =31
const int SHIFT=5;
int num[1+N/32];
bool test(int i){
return num[i>>SHIFT] & (1<<(i&MAXN));
}

int main()
{
memset(num,0,sizeof(num));
int x;
while(cin>>x){
num[x>>SHIFT]|=(1<<(x&MAXN)); //等效于 num[x/32]|=(1<<(i%32))
}
for(int i=0;i<=N;i++){
if(test(i))
cout<<i<<endl;
}
return 0;
}

开篇——给磁盘文件排序