剑指Offer 40—最小的k个数

题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。

因此，只需要将数组划分为 最小的k个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标。

根据快速排序原理，如果某次哨兵划分后 基准数正好是第 k+1 小的数字 ，那么此时基准数左边的所有数字便是题目所求的 最小的 k 个数 。

根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于 k ，若 true 则直接返回此时数组的前 k 个数字即可。

算法流程：

getLeastNumbers() 函数：

1. 若 k 大于数组长度，则直接返回整个数组；
2. 执行并返回 quick_sort() 即可；

quick_sort() 函数： 

注意，此时 quick_sort() 的功能不是排序整个数组，而是搜索并返回最小的 k 个数。

1、哨兵划分： 

• 划分完毕后，基准数为 arr[i] ，左 / 右子数组区间分别为 [l, i - 1], [i + 1, r]；

2、递归或返回：

• 若 k < i，代表第 k+1 小的数字在 左子数组 中，则递归左子数组；

• 若 k>i ，代表第 k+1 小的数字在 右子数组 中，则递归右子数组；
• 若 k=i ，代表此时 arr[k] 即为第 k+1 小的数字，则直接返回数组前 k 个数字即可；

class Solution 
{
public:
    vector getLeastNumbers(vector& arr, int k) 
    {
        if(k>=arr.size())
        {
            return arr;
        }
        return quick_sort(arr,k,0,arr.size()-1);
    }
    vector quick_sort(vector& arr,int k,int l,int r)
    {
        int i=l,j=r;
        //以基准元素(arr[l])为中点，将数组arr划分成左右两个字数组
        while(i=arr[l])
                j--;
            //从左往右，查找第一个大于基准元素的元素
            while(ii)//最小的k个数在右子数组里面
        {
            return quick_sort(arr,k,i+1,r);
        }
        if(k res(arr.begin(),arr.begin()+k);
        return res;

    }
};