首页 > 代码库 > 最小的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个数