求的数组的topN

发布时间:2016-12-8 2:30:24 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"求的数组的topN",主要涉及到求的数组的topN方面的内容,对于求的数组的topN感兴趣的同学可以参考一下。

/** 查找最小的k个元素 题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4 **/ #include <vector> #include <iostream> #include <algorithm> //swap void swap(int& left,int& right) { int tem=left; left=right; right=tem; } //shift down void shift_down(int* arr,int size,int begin_pos) { int tem_index; while(begin_pos*2+1<size) { tem_index=arr[begin_pos*2+1]>arr[begin_pos]?begin_pos:begin_pos*2+1; if(begin_pos*2+2<size) { if(arr[begin_pos*2+2]<arr[tem_index]) tem_index=begin_pos*2+2; } if(begin_pos==tem_index) break; swap(arr[begin_pos],arr[tem_index]); begin_pos=tem_index; } } //min heap void make_heap(int* arr,int n) { for(int i=n/2-1;i>=0;--i) shift_down(arr,n,i); } //min top n void top_n(int* arr,int size,int n,std::vector<int>& vec) { if(n>=size) return ; int tem=n; make_heap(arr,size); while(tem) { vec.push_back(arr[0]); swap(arr[0],arr[size-n+tem-1]); shift_down(arr,size-n+tem-1,0); --tem; } } int main(int argc,char* argv[]) { int arr[]={23,2,1,3,532,2,63,23}; std::vector<int> vec; top_n(arr,sizeof(arr)/sizeof(int),4,vec); std::for_each(vec.begin(),vec.end(),[](const int& val) { std::cout<<val<<" "; } ); std::cout<<std::endl; system("PAUSE"); return 0; }

上一篇:Yet Another PhotoMosaic Generator
下一篇:吴思:王朝末日中的“崇祯死弯”

相关文章

相关评论