题目描述：
输入：一亿个整数，有重复的数字，整数保存在一个文件中
输出：文件中最大的k个数
限制：尽量以最快的速度完成任务。
具体解决方法：
1. 位图解决
位图为用比特位来存储数据，如果i比特位为1，则该位在表示整数i，为0，则不是
用该方法主要提供三个函数接口：设置比特位：set_bit(int *data, int num)
清除比特位：clr_bit(int *data, int num)
获得某个比特位：get_bit(int *data, int num)
这些函数具体实现都用位操作实现
具体实现代码：
#include <iostream>
#include <cstdio>
#include <sys/time.h>
#include <cstdlib>
using namespace std;
#define BITSIZE 32
#define SHIFT 5
#define SIZE 10000000
void set_bit(int *data, int num)
{
data[num>>SHIFT] |= 0x01<<(num&(BITSIZE-1));
}
void clr_bit(int *data, int num)
{
data[num>>SHIFT] &= ~(0x01<<(num&(BITSIZE-1)));
}
int get_bit(int *data, int num)
{
return (data[num>>SHIFT] & (0x01<<(num&(BITSIZE-1))));
}
int main(void)
{
FILE *fp;
int k=0;
fp=fopen("10_million_data.txt", "r");
struct timeval start, end;
int a[312500]={0};
int num=0;
gettimeofday(&start, NULL);
while(!feof(fp))
{
fscanf(fp, "%d", &num);
if(feof(fp)) break;
set_bit(a, num);
}
for(long long int i=SIZE; i>=1; i--)
{
if(get_bit(a, i))
{
++k;
if(k>10) break;
cout << i << " ";
}
}
cout << endl;
gettimeofday(&end, NULL);
float t_time = end.tv_sec-start.tv_sec+(end.tv_usec-start.tv_usec)/1000000.0;
cout << "time used : " << t_time << endl;
return 0;
}
2. 用标准库关联性容器set实现
说明：set中的元素是有序的，默认是升序的，且数组元素不重复
边插入边排序，具体代码如下：
int main(void)
{
set<int> s;
FILE *fp;
int num=0;
fp=fopen("10_million_data.txt", "r");
struct timeval start, end;
gettimeofday(&start, NULL); //linux系统调用函数
while(!feof(fp))
{
fscanf(fp, "%d", &num);
s.insert(num);
}
gettimeofday(&end, NULL);
float t_time = end.tv_sec-start.tv_sec+(end.tv_usec-start.tv_usec)/1000000.0;
cout << t_time << endl;
//set<int>::iterator it=s.begin();
//for(; it!=s.end(); ++it)
return 0;
}
3. 用10个小根堆实现查找较大的10个数，时间复杂度为O(10000000*logk)
思路：先用文件中的前十个数初始化为一个10个元素的小根堆，默认为较大的10个数，再逐个从文件中读文件，比根顶元素大就调整小根堆，知道文件读完为止
具体实现代码：
void exch(long int &a, long int &b) { long int temp=a; a=b; b=temp; }
void sink(long int *data, int pos)
int l=2*pos;
if(l<data[0] && data[l]>data[l+1]) l++;
if(data[l]>data[pos]) break;
exch(data[l], data[pos]);
pos=l;
}
}
void swim(long int *data, int pos)
{
while(pos>1 && data[pos/2]<data[pos])
{
exch(data[pos/2], data[pos]);
pos=pos/2;
}
}
void select_topk(FILE *pf, long int *data)
{
int i=0, j=10;
long int num=0;
for(i=k/2; i>=1; i--)
sink(data, i);
while(!feof(pf))
{
fscanf(pf, "%ld", &num);
if(feof(pf)) break;
j++;
if(num>data[1])
{
exch(data[1], num);
sink(data, 1);
}
}
cout << j << endl;
}
int main(void)
{
long int topk[k+1]={k};
struct timeval start, end;
long int num=1;
FILE *pf;
//pf=fopen("3milliondata.txt", "r");
pf=fopen("10_million_data.txt", "r");
gettimeofday(&start, NULL);
for(long int i=1; i<=10; i++)
{
fscanf(pf, "%ld", &topk[i]);
}
select_topk(pf, topk);
gettimeofday(&end, NULL);
float time=end.tv_sec-start.tv_sec+(end.tv_usec-start.tv_usec)/1000000.0;
printf("time is used %f\n", time);
for(int i=1; i<=k; i++)
cout << topk[i] << " ";
cout << endl;
return 0;
}
三中方案的运行时间比较，其中第三种方法输出带有重复的元素
另外在小数据时寻找mink或者maxk,可以考虑使用快速排序的思想来实现，具体代码如下
void exch(int &a, int &b)
{
int temp=a;
a=b;
b=temp;
}
int Less(int a, int b) { return (a<b ? 1 : 0); }
int randint(int min, int max)
{
return (rand()%(max-min+1)+min);
}
void qsort_mink(int *data, int l, int h, int k)
{
int i=l, j=h+1;
exch(data[l], data[randint(l+1, h)]);
int key = data[l];
while(1)
{
while(Less(data[++i], key)) if(i==h) break;
while(!Less(data[--j], key)) if(j==l) break;
if(i>j) break;
exch(data[i], data[j]);
}
exch(data[l], data[j]);
if(j>k)
qsort_mink(data, l, j-1, k); //在j的左半边寻找
if(j<k)
qsort_mink(data, j+1, h, k); //在j的右半边寻找
}
该方法是时间复杂度为O(nlogn)
总结：
从运行结果中看出：小根堆排序实现 < 位图实现 < C++STL实现
所以topk问题一般用小根堆或大根堆实现，或者可以使用位图(当然数字一大时就会出现内存不够的现象)