【剑指 Offer 40】最小的k个数-Toy模板网

这篇具有很好参考价值的文章主要介绍了【剑指 Offer 40】最小的k个数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

输入整数数组 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]

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

思考：

找到一个数组中最小的 k 个数，得出要对该数组进行排序
排序算法该如何选择呢？
根据题目要求，不要求输出的这 k 个数的顺序，考虑使用快速排序
因为是输出最小的 k 个数，索引从 0 开始，所以当基准数为 k+1 小的数时，这个基准数的左边子数组就是我们要找的 k 个数，也就是基准数索引为 k 时
使用快速排序划分子数组，每划分一次看基准数索引是否等于 k
若 k < 基准数索引，代表第 k+1 小的数字在左子数组中，则递归左子数组
若 k > 基准数索引，代表第 k+1 小的数字在右子数组中，则递归右子数组
否则直接返回数组前 k 个数字文章来源地址https://www.toymoban.com/news/detail-637331.html

题解：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length) return arr;
        return quickSort(arr, k, 0, arr.length-1);
    }

    private int[] quickSort(int[] arr, int k, int l, int r){
        int i = l, j = r;
        while (i<j){
            while (i<j && arr[j] >= arr[l]) j--;
            while (i<j && arr[i] <= arr[l]) i++;
            swap(arr,i,j);
        }
        swap(arr,i,l);
        //基准数索引 > k,递归左子数组
        if (i > k) return quickSort(arr, k, l, i-1);
        //基准数索引 < k,递归右子数组
        if (i < k) return quickSort(arr, k, i+1, r);

        return Arrays.copyOf(arr, k);
    }
    //交换方法
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}