跟着姚桑学算法-最小的k个数

题. 最小的k个数

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

注意：

输出数组内元素请按从小到大顺序排序;

数据范围
1≤k≤n≤1000
样例

输入：[1,2,3,4,5,6,7,8] , k=4

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

【题解】-- 堆排序

要维护一个大小为k的大根堆，将数组元素都push进堆，当堆中的数大于k时弹出堆顶元素。
注意 弹出堆顶的顺序是从大到小的k个数，要进行逆序操作。

【解2】--- 快速排序

也可以运用快速排序的思想，每次快速选择会将一个数放置到正确的位置----即满足左边的数都比它小，右边的数都比它大，因此可以对原数组做k次快速选择。

复杂度分析：

建堆的时间复杂度是O(logk)，要进行n次建堆的操作。

C++代码实现：

// 堆排序
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        priority_queue<int> heap;
        for(auto x : input)
        {
            heap.push(x);
            if(heap.size() > k) heap.pop(); 
        }
        while(heap.size())
        {
            res.push_back(heap.top());
            heap.pop();
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

// 快速排序
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        for(int i = 1;i <= k;i++)
            res.push_back(quick_select(input,0,input.size()-1,i));
        return res;
    }

    int quick_select(vector<int>& q,int l,int r,int k)
    {
        if(l >= r) return q[l];
        int i = l-1,j = r+1,x = q[l+r >> 1];
        while(i < j)
        {
            do i++;while(q[i] < x);
            do j--;while(q[j] > x);
            if(i < j) swap(q[i],q[j]);
        }
        if(k <= j-l+1) return quick_select(q,l,j,k);
        else return quick_select(q,j+1,r,k-(j-l+1));
    }

};