首页 > 代码库 > 最小的k个数
最小的k个数
题目:输入n个整数,找出其中最小的k个数字。例如输入4,5,1,6,2,4,7,3这8个数字,则最小的4个数字是1,2,3,4.
分析:最简单办法,将n个数排序,然后最前面的k个就是最小的k个数字。这种算法时间复杂度为O(nlogn),还可以进一步提升。
方法一:类似与“数组中出现次数超过一半的数字”中的思想,时间复杂度为O(n),代码如下:
void GetLeastNumbers(int* input,int n,int* output,int k) { if(input==NULL||output==NULL||k>n||n<=0||k<=0) return; int start=0; int end=n-1; int index=Partition(input,n,start,end); while(index!=k-1) { if(index>k-1) { end=index-1; index=Partition(input,n,start,end); } else { start=index+1; index=Partition(input,n,start,end); } } for(int i=0;i<k;i++) output[i]=input[i]; }
同样的,这种方法有限制,就是要改动数组。如果不能改动数组,则可以用下面这种方法。
方法二:创建一个大小为k的数据容器来存储最小的k个数字,接下来我们每次输入n个整数中的一个数,如果容器没有满,则直接放入,如果满了,则找出k个数中的最大数,然后和这个数比较大小,如果比最大数大,则直接抛弃这个数,如果较小,则替换最大数。时间复杂度为O(nlogk),特别适合处理海量数据。实现如下:
typedef multiset<int,greater<int>> intSet; typedef multiset<int,greater<int>>::iterator setIteeator; void GetLeastNumbers(const vector<int>& data,intSet& leastNumbers,int k) { leastNumbers.clear(); if(k<1||data.size()<k) return; vector<int>::const_iterator iter=data.begin(); for(;iter!=data.end();++iter) { if((leastNumbers.size())<k) leastNumbers.insert(*iter); else { setIterator iterGreatest=leastNumbers.begin(); if(*iter<*(leastNumbers.begin())) { leastNumbers.erase(iterGreatest); leastNumbers.insert(*iter); } } } }
本文出自 “仙路千叠惊尘梦” 博客,请务必保留此出处http://secondscript.blog.51cto.com/9370042/1586198
最小的k个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。