题目

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

解析

本题主要有三种解法
方法一：排序，对原数组从小到大排序后取出前 kk 个数即可。
方法二：堆，例如c++中就可以直接使用priority_queue优先队列，即大根堆
方法三：快排思想，借鉴快排的思想，具体参考“参考代码”
每日一题：快速排序

参考代码

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(k == 0 || arr.size() == 0)
        {
            return vector<int>(0);
        }

        return quickSort(arr, 0, arr.size()-1, k-1);
    }

    // 函数传入待排序数组 nums
    // 排序区间的左端点 left
    // 排序区间的右端点 right
     vector<int> quickSort(vector<int>& nums,int left, int right , int index){

        // 调用函数 partition，将 left 和 right 之间的元素划分为左右两部分
        int mid = partition(nums,left,right);

        // 如果 mid 下标恰巧为 index，那么找到了最小的 k 个数
        if (mid == index) {
            // 直接返回
            vector<int> res;
            res.insert(res.begin(),nums.begin(),nums.begin()+mid+1);
            return res;
           // return Arrays.copyOf(nums, mid + 1);

        // 如果 mid 下标大于 index，那么说明需要在左侧元素中去切分
        }else if( mid > index ){

            // 对 mid 左侧的元素进行快速排序
            return quickSort(nums,left,mid - 1, index );
        }else{

            // 对 mid 右侧的元素进行快速排序
            return quickSort(nums,mid + 1,right, index );
        }

    }

    int partition(vector<int>& nums, int left ,int right){

        // 经典快速排序的写法
        // 设置当前区间的第一个元素为基准元素
        int pivot = nums[left];

        // left 向右移动，right 向左移动，直到 left 和 right 指向同一元素为止
        while( left < right ){

            // 只有当遇到小于 pivot 的元素时，right 才停止移动
            // 此时，right 指向了一个小于 pivot 的元素，这个元素不在它该在的位置上
            while( left < right && nums[right] >= pivot ){
                // 如果 right 指向的元素是大于 pivot 的，那么
                // right 不断的向左移动
                right--;
            }

            // 将此时的 nums[left] 赋值为 nums[right]
            // 执行完这个操作，比 pivot 小的这个元素被移动到了左侧
            nums[left] = nums[right];


            // 只有当遇到大于 pivot left 才停止移动
            // 此时，left 指向了一个大于 pivot 的元素，这个元素不在它该在的位置上
            while( left < right && nums[left] <= pivot){
                // 如果 left 指向的元素是小于 pivot 的，那么
                // left 不断的向右移动
                left++;
            }

            // 将此时的 nums[right] 赋值为 nums[left]
            // 执行完这个操作，比 pivot 大的这个元素被移动到了右侧
            nums[right] = nums[left];

        }

        // 此时，left 和 right 相遇，那么需要将此时的元素设置为 pivot
        // 这个时候，pivot 的左侧元素都小于它，右侧元素都大于它
        nums[left] = pivot;

        // 返回 left
        return left;

    }
};