最小的k个数

方法一：用vector中的sort函数进行排序

思路：

vector<int>input;
sort(input.begin(),input.end())
return vector<int>({input.begin(),input.begin()+k});

代码：

class Solution{
    public:
    vector<int> GetLeastNumbers_Solution(vector<int> input,int k){
        vector<int> res;
        if(k==0||k>input.size()){
            return res;
        }
        //vector中自带的sort函数进行排序
        sort(input.begin(),input.end());
        //返回排序后的前k小的数
        return vector<int>({input.begin(),input.begin()+k});
    }
};

方法二：用k大小的堆构造一个优先队列

思路：

1.只要优先队列中的元素的个数还是小于k，则 直接将数插入队列中

2.否则就与队首的元素进行比较，如果比队首的元素小，则让队首元素出队列

代码：

class Solution{
    public:
    //定义一个容器用来存排序后的元素的数组，传入需要排序的数组，以及输出第k个小的数
    vector<int> GetLeastNumbers_Solution(vector<int> input,int k){
        //定义一个数组用来存排序的k个数
       vector<int>res;
       //如果需要输出的是第0小的数，或需要输出的k个数比总的元素少，则直接返回
       if(k==0||k>input.size()){
        return res;
       }
       //定义一个优先队列
       priority_queue<int,vector<int>> q;
       //遍历整个序列，如果发现优先队列中的元素个数少于k，那么就直接将元素放入队列中
       //否则就与队首的元素进行比较，如果发现队首的元素大于想要的插入的数，就让队首出队，
       //让新的这个元素插入队尾
       for(const int val:input){
        if(q.size()<k){
            q.push(val);
        }else{
            if(q.top()>val){
                q.pop();
                q.push(val);
            }
        }
       }
       //将优先队列中的所有元素插入容器res中
       while(!q.empty()){
        res.push_back(q.top());
        q.pop();
       }
       return res;
    }
};

方法三：快排+二分

思路：

对数组[l, r]一次快排partition过程可得到，[l, p), p, [p+1, r)三个区间,[l,p)为小于等于p的值[p+1,r)为大于等于p的值。

然后再判断p，利用二分法

如果[l,p), p，也就是p+1个元素（因为下标从0开始），如果p+1 == k, 找到答案

如果p+1 < k, 说明答案在[p+1, r)区间内，

如果p+1 > k , 说明答案在[l, p)内

代码：

class Solution{
    public:
    int partition(vector<int> &t,int l,int r){
        //设置一个基准数：这里设置最后一个数为基准数
        //设置两个同方向的指针：i=0(找比基准大的数)，j=0(找比基准小的数)
        int temp=t[r-1];
        int i=l;
        //让j指针遍历除了最后一个数之外的所有的数
        //如果发现一个小于基准的数，就将其与i对应的数交换，i与j指针都向后移动一位
        //否则就将j移动，直到找到一个比基准小的数，再进行就交换
        for(int j=l;j<r-1;j++){
            if(t[j]<temp){
                swap(t[i++],t[j]);
            }
        }
        //最后将最后一个数（不一定是原先的temp），与i指向的数交换
        swap(t[r-1],t[i]);
        return i;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input,int k){
        vector<int>res;
        if(k==0||input.size()<k){
            return res;
        }
        //快排设置两个指针：左指针l=0，右指针r=input.size()
        int l=0,r=input.size();
        //快排：只要所有指针还没有相交，就继续
        while(l<r){
            int p=partition(input,l,r);
        //由于下标从0开始，所以元素个数时p+1
        //如果够了k个，就直接返回左区间
            if(p+1==k){
                return vector<int>({input.begin(),input.begin()+k});
            }
            //如果还不够k个元素，就继续再右区间中去找，所以更新l=p+1
            if(p+1<k){
                l=p+1;
            }else {
                //如果超过了，就让 右指针指向p，因为答案在[l,p)之间
                //由于传入p的时候会取p-1的数为基准，所以是在[l,p)中找
                r=p;
            }
        }
      
        return res;
    }
};