如何从1G数据中找出最大的1000个？
1G数据，浮点数，怎样快速查找出最大的1000个数？内存足够大。
忘高手解答。
[解决办法]
定义一个1000大小的数组 a,
遍历这1G数据
逐个把数据放到 a 中, (a 中的数据从大到小排列) 把小的数据挤出
[解决办法]
先从大到小排序，再取出前面1000个就可以了。不要搞那么复杂，排个序又不复杂，况且有现成的函数可用。
[解决办法]
全部排序会很慢
用STL的 partial_sort
[解决办法]
这种帖子回了三四次了。
[解决办法]
//这个应该比全部排序要快点#include <iostream>#include <list>#include <algorithm>using namespace std;#include <time.h>template <class T>void find_max(T* datas,size_t ds,list<T>& max,size_t ms){ size_t i; for(i=0;i< ms;++i) { max.push_back(datas[i]); } max.sort( greater<T>());//降序 for ( i = ms; i < ds; ++i)// 20 19 18 16 15 10 8 7// { if(datas[i] < *max.begin())//算法效率的关键在,对小于这ms个数的数直接放弃 continue; list<T>::iterator iter; for(iter=max.begin();iter != max.end();++iter) { if(datas[i] > *iter) { max.insert(iter,datas[i]); max.pop_back(); break; } } }}int main(){ srand(time(0));// const int size = 100; float* datas = new float[size]; int i; for ( i = 0; i < size; ++i) { datas[i] = (float)rand(); //cout<<datas[i]<<' ' ; } const int m=10; float max[m] = {0.0}; //排序后输出最大的m个数,测试对比用. //sort(&datas[0],&datas[size]); //for ( i = size-1; i >=size-m; --i) //{ // cout<<datas[i]<<' ' ; //} //cout<<endl; list<float> fmax; find_max(datas,size,fmax,m); for (list<float>::iterator iter=fmax.begin();iter!=fmax.end();++iter) cout<<*iter<<" "; cout<<endl; delete[] datas; return 0;}
[解决办法]
我有个猜想,请高手指正
利用快速排序中划分,m=1000
(1)一次划分结束后,可以得到一个大数划分和一个小数划分,并且划分元素所在的索引n表示它是第n大元素.
(2)若划分后n>>m,则再在大数划分中选择划分元素继续划分得到该划分中n个最大数,转(2)
(3)若划分后n<<m,则m=m-n再在小数划分中选择划分元素继续划分得到该划分中n个最大数,转(2)
(4)若n接近m,则只需要在现在划分下的大数或小数划分中找出|n-m|个大数,或去掉|n-m|个小数
(5)若n=m,则1000个最大数找出
其主要思想是尽可能不去处理较小的数,通过划分后,不断向目标大数划分逼近,且每次划分后的处理量减少,提高性能.
以上为个人猜想,请指教!
[解决办法]
这种类似问题可以出个专集了。。
。。用数论推个理论出来，大家按那标准做就最好了。
[解决办法]
to iambic: "楼上的你的partition很典型。但是请考虑下最坏情况。"
sliuyin的方法是在快排基础上的针对这道题一种改进,最坏情况也不过快排的
最坏情况啊.
我觉得他的方法还行.个人看法,请iambic指点.
[解决办法]
1:想把总的数据等分(等分多少分,看实际要求),每一分相当于一组
2:对等分后的每一组数据进行排序(降序)
3:然后在这些组中检最大的1000个数据
[解决办法]
肯定不能进行排序了，星羽那个改一下就是很快了，如果用list来实现的话，在挤出数据那里又会快一点