输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

思路：
快速排序

题目只要求返回最小的k个数，因此可以使用快排，如果某次哨兵划分后基准数正好是第k+1小的数，则基准左边的所有数字便是题目所求的最小的k个数。于是在每次哨兵划分后，判断基准数在数组中的索引是否等于k，若为true则直接返回数组的前k个数即可。

AC代码：（C++）

class Solution {
   public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k >= arr.size()) return arr;
        return quickSort(arr, k, 0, arr.size() - 1);
    }
    vector<int> quickSort(vector<int>& arr, int k, int left, int right) {
        int i = left, j = right;
        while (i < j) {
            while (i < j && arr[j] >= arr[left]) j--;
            while (i < j && arr[i] <= arr[left]) i++;
            swap(arr[i], arr[j]);
        }
        swap(arr[i], arr[left]);
        if (k < i) return quickSort(arr, k, left, i - 1);
        if (k > i) return quickSort(arr, k, i + 1, right);
        vector<int> res;
        res.assign(arr.begin(), arr.begin() + k);
        return res;
    }
};