上亿个数据保存在硬盘中,找出最大的N个
请问一个算法问题:
上亿个数据保存在硬盘中,找出最大的N个。
这个算法如何实现?
[解决办法]
先选N个元素组成一个小根堆,然后遍历剩下的数据,如果第i个元素M大于小根堆的根结点,就删除这个根结点,并将元素M插入这个小根椎,最后,小根堆中的元素就是最大的N个元素。
[解决办法]
#include <set>#include <iostream>#include <fstream>using namespace std;#define N 10int main(int argc, char* argv[]){ set<int> set_MAX_N; ifstream inFile("test.txt"); int nTemp; while(inFile >>nTemp) { set_MAX_N.insert(nTemp); if(set_MAX_N.size() > N) { set_MAX_N.erase(set_MAX_N.begin()); } } for(set<int>::iterator it = set_MAX_N.begin();it != set_MAX_N.end(); it ++) cout<< *it <<endl; while(1); return 0;}
[解决办法]
顺着7楼的思路想了下
如果所有数据范围不大的话 比如在1万以内
可以用桶 找出地K大的数
过程:
扫一遍N个数,放入桶中并计个数
扫一遍所有桶,找出第K大的数X
再扫一遍桶 输出计数>0的数 直到扫到X
最糟糕的情况:N+2*Range Range就是数据范围