M40-最小的k个数.md

一、堆

思路：

使用大根堆，大根堆每次pop()都会弹出最大值，维护一个始终只有k个元素的大根堆，然后再将剩下的元素与top()比较

大根堆(默认)，top()总是最大的值

priority_queue<int, vector<int>, less<int> >

小根堆，top()总是最小的值（可用来做最大的k个数这种题）

priority_queue<int, vector<int>, greater<int> >

class Solution 
{
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) 
    {
        if (arr.size() == 0 || k <= 0) return {};
        //存放结果的数组
        vector<int> ans(k, 0);
        //大根堆
        priority_queue<int> h;
        //将k个数放入堆中
        for (int i = 0; i < k; i++)
        {
            h.push(arr[i]);
        }
        //将剩下的元素分别于h.top()比较
        for (int j = k; j < arr.size(); j++)
        {
            //若当前元素小于堆中最大值，弹出堆中最大值，将该元素入堆
            if (arr[j] < h.top())
            {
                h.pop();
                h.push(arr[j]);
            }
        }
        //将堆中的k个元素放入数组中返回
        for (int i = 0; i < k; i++)
        {
            ans[i] = h.top();
            h.pop();
        }
        return ans;
    }
};

二、分治法（快速选择）

思路

找k个数，那么第k个数的下标为k-1 快速排序每进行一轮，基准元素的左侧数组都是小于基准元素的，右边都是大于基准元素的。返回基准元素的下标index，与k-1对比：

1.若`index == k - 1`，那么index即为第k个数，直接返回
2.若`index < k - 1`，那么第k个数在基准元素的右边，对右侧数组再次进行快速排序
3.若`index > k - 1`，那么第k个数在基准元素的左边，对左侧数组再次进行快速排序

直到找到index == k - 1

class Solution 
{
public:
    //快排划分函数
    void partion(vector<int>& arr, int start, int end, int pos)
    {
        if (start >= end) return;
        int left = start;
        int right = end;
        int pivot = arr[start];
        //记录基准元素的下标
        int index = left;
        while (left < right)
        {
            while (left < right && arr[right] > pivot)
            {
                right--;
            }
            if (left < right)
            {
                swap(arr[right], arr[left]);
                index = right;
                left++;
            }
            while (left < right && arr[left] < pivot)
            {
                left++;
            }
            if (left < right)
            {
                swap(arr[left], arr[right]);
                index = left;
                right--;
            }
        }
        //等于，index即为所求的pos,index为第k个数
        if (index == pos) return;
        //pos的在右边的数组，再快排右侧数组寻找pos
        if (index < pos) partion(arr, index + 1, end, pos);
        //pos的在左边的数组，再快排左侧数组寻找pos
        if (index > pos) partion(arr, start, index - 1, pos);
    }
    vector<int> getLeastNumbers(vector<int>& arr, int k) 
    {
        //最小的k个数，第k个的下标为k-1，所以要寻找k-1的下标
        partion(arr, 0, arr.size() - 1, k - 1);
        vector<int> ans;
        for (int i = 0; i < k; i++)
        {
            ans.push_back(arr[i]);
        }
        return ans;
    }
};
``