第k大元素

输入n个整数，找出其中最小的k个数。

注意：

数据保证k一定小于等于输入数组的长度;
输出数组内元素请按从小到大顺序排序;
样例
输入：[1,2,3,4,5,6,7,8] , k=4

输出：[1,2,3,4]

常见解法：

• 排序
• 借助堆: 借助大小为K的堆，从而实现快速比较。
• 线性选择（快排思想） —普通：最坏的时间复杂度$O(lgn)$
• 线性选择（快排思想） —基于中位数的select升级：借助基于中位数的select算法来选择枢点，可以尽可能的2分问题，从而使得最坏的时间复杂度控制在$O(n)$

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;//注意这里要加const，下面才可以定义全局变量q[]
int q[N];
 
int quick_choose(int l, int r, int k){
    if(l==r) return q[l];//区间里只有一个数
    
    int i = l-1, j = r+1, x = q[(l+r)/2];
    while(i<j){
     while(q[++i]<x);
     while(q[--j]>x);  
     if(i<j){
         swap(q[i], q[j]);
     }
    }
    //
    int sl = j-l+1;//左区间多少数
    if(k<=sl) return quick_choose(l,j,k);
    if(k>sl) return quick_choose(j+1,r,k-sl);
}
 
int main(){
    int n,k;
    cin >> n >> k;
    for(int i=0; i<n; i++){
        cin >> q[i];
    }
    cout << quick_choose(0,n-1,k) << endl;
    
}

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int, vector<int>, less<int>> q; //大顶堆
        
        for (int i = 0; i < input.size(); ++i) {
            if (q.size() < k) {
                q.push(input[i]);
            }
            else {
                if (input[i] < q.top()) {
                    q.pop();
                    q.push(input[i]);
                }
            }
        }
        
        vector<int> res;
        
        while (q.size()) {
            res.push_back(q.top());
            q.pop();
        }
        
        reverse(res.begin(), res.end());
        return res;
    }
};