[剑指offer]最小的K个数

ゞ浴缸里的玫瑰 2021-12-19 22:29 322阅读 0赞

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

**最大堆 时间复杂度O（nlogk）**

class Solution {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
            int len=input.size();
            //notice range of len and k
            if(len<=0 || k>len || k<=0) return vector<int>();
            vector<int> res(input.begin(),input.begin()+k);
    /*
            vector<int> res;
            if(len<=0 || k>len || k<=0) return res;
            for (int i = 0; i < k; i++) res.push_back(input[i]);
    */
            //建堆
            make_heap(res.begin(),res.end());
             
            for(int i=k;i<len;i++)
            {
                if(input[i]<res[0])
                {
                    //先pop,然后在容器中删除
                    pop_heap(res.begin(),res.end());
                    res.pop_back();
                    //先在容器中加入，再push
                    res.push_back(input[i]);
                    push_heap(res.begin(),res.end());
                }
            }
            //使其从小到大输出
            sort_heap(res.begin(),res.end());
             
            return res;
             
        }
    };

**Partition快排核心思想，时间复杂度O(n)**

class Solution {
    public:
        int Partition(vector<int>& input, int begin, int end){
            int low=begin;
            int high=end;
            int pivot=input[low];
            while(low<high){
                while(low<high && pivot<=input[high])high--;
                input[low]=input[high];
                while(low<high && pivot>=input[low])low++;
                input[high]=input[low];
            }
            input[low]=pivot;
            return low;
        }
         
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
            int len=input.size();
            if(len==0||k>len || k<=0) return vector<int>();
            if(len==k) return input;
             
            int start=0;
            int 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);
                }
            }
             
            vector<int> res(input.begin(), input.begin() + k);
             
            return res;
        }
     
    };

**红黑树：multiset集合  利用仿函数改变排序顺序 时间复杂度O（nlogk） **

class Solution {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
            int len=input.size();
            if(len<=0 || k>len || k<=0) return vector<int>();
             
            //仿函数中的greater<T>模板，从大到小排序
            multiset<int, greater<int> > leastNums;
            vector<int>::iterator vec_it=input.begin();
            for(;vec_it!=input.end();vec_it++){
                //将前k个元素插入集合
                if(leastNums.size()<k)
                    leastNums.insert(*vec_it);
                else{
                    //第一个元素是最大值
                    multiset<int, greater<int> >::iterator greatest_it=leastNums.begin();
                    //如果后续元素<第一个元素，删除第一个，加入当前元素
                    if(*vec_it<*(leastNums.begin())){
                        leastNums.erase(greatest_it);
                        leastNums.insert(*vec_it);
                    }
                }
            }
             
            return vector<int>(leastNums.begin(),leastNums.end());
        }
    };