欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

topK问题

程序员文章站 2022-03-24 17:35:26
...

剑指offer最小的k个数

法一:快速排序

注意partition函数的vector要加引用,同时需要判断数组长度和k的大小。

时间复杂度为O(n),但会修改数组

class Solution {
public:
    
    int Partition(vector<int> &input,int start,int end)
    {
            int pivot=input[start];
            int left=start;
            int right=end;
            while(left<right)
            {
                while(left<right&&input[right]>=pivot)
                    --right;
                input[left]=input[right];
                while(left<right&&input[left]<=pivot)
                    ++left;
                input[right]=input[left];
            }
            input[left]=pivot;
            return left;
    }
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if((input.size()<k)||(k<=0)||input.size()<=0)
            return res;
        else if(input.size()==k)
            return input;
        int len=input.size();
        int start=0,end=len-1;
        int index=Partition(input,start,end);
        while(index!=k-1)
        {
            if(index>k-1)
            {
                end=index-1;
                index=Partition(input,start,end);
            }
            else
            {
                start=index+1;
                index=Partition(input,start,end);
            }
        }
        
        for(int i=0;i<k;i++)
        {
            res.push_back(input[i]);
        }
        return res;
    }
};

法二 用堆的思维

考虑到需要建堆很麻烦,就用multiset代替,因为multiset的基于红黑树实现的,其删除插入元素时间复杂度都是logn。

首先维护一个有序数组(multiset中数据有序且可以重复),数组容量为k

遍历原数组,如果此时有序数组未满,就直接加入数组,Multiset会自动调整数组有序。如果数组已满,就比较待加入元素a和数组最大元素b,如果a<b,就把b剔除,把a加入数组中。否则不做处理。

时间复杂度为O(klogn),k为最值个数,n为所有元素的个数。

set<int> s;   
multiset<int> s;    //自动升序排序

set<int,greater<int>> s;
multiset<int,greater<int>> s;    //自动降序排序
    multiset<int,greater<int> > intset;
    vector<int> GetLeastNumberCore(vector<int> &input,multiset<int,greater<int> > &intset,int k)
    {
        intset.clear();
        vector<int>::iterator it;
        for(it=input.begin();it!=input.end();it++)
        {
            if(intset.size()<k)
                intset.insert(*it);
            else
            {
                multiset<int,greater<int> >::iterator it1=intset.begin();   //最大值
                if(*it<*it1)
                {
                    intset.erase(it1);
                    intset.insert(*it);
                }
            }
        }
        vector<int> res;
        multiset<int,greater<int> >::iterator it1=intset.begin();
        for(;it1!=intset.end();it1++)
        {
            res.push_back(*it1);
        }
        return res;
    }
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(input.size()<=0||k<=0||input.size()<k)
            return res;
        else if(input.size()==k)
            return input;
        else
        {
            res=GetLeastNumberCore(input,intset,k);
            return res;
        }
    }