题目描述

解题思路

归并排序

public int[] getLeastNumbers(int[] arr, int k) {
    // 归并排序
    mergeSort(arr, 0, arr.length - 1);
    return Arrays.copyOf(arr, k);
}
/**
         * 归并排序
         *
         * @param nums
         * @param l
         * @param r
         */
public void mergeSort(int[] nums, int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = (l + r) / 2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    int[] tempArray = new int[r - l + 1];
    for (int i = l; i <= r; i++) {
        tempArray[i - l] = nums[i];
    }
    int i = 0, j = mid - l + 1; // 分别指向左右子数组的首个元素
    for (int k = l; k <= r; k++) {
        if (i == mid - l + 1) {
            nums[k] = tempArray[j++];
        } else if (j == r || tempArray[j] >= tempArray[i]) {
            nums[k] = tempArray[i++];
        } else if (tempArray[j] < tempArray[i]) {
            nums[k] = tempArray[j++];
        }
    }
}

快速排序

public int[] getLeastNumbers(int[] arr, int k) {
    // 归并排序
    // mergeSort(arr, 0, arr.length - 1);
    // 快排
    quickSort(arr,k, 0, arr.length - 1);
    return Arrays.copyOf(arr, k);
}
/**
         * 快速排序
         *
         * @param arr
         * @param l
         * @param r
         */
public void quickSort(int[] arr, int l, int r) {
    if (l >= r) {
        return;
    }
    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, l, i);    // 交换最后位置
    // 递归左右数组进行快速排序
    quickSort(arr, l, i - 1);
    quickSort(arr, i + 1, r);
}
public void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

基于快速排序的数组划分

题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为 最小的 k 个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标。
根据快速排序原理，如果某次哨兵划分后 基准数正好是第 k+1 小的数字 ，那么此时基准数左边的所有数字便是题目所求的 最小的 k 个数 。
根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于 k ，若 true 则直接返回此时数组的前 k 个数字即可。

步骤

哨兵划分：
划分完毕后，基准数为 arr[i] ，左 / 右子数组区间分别为 [l, i - 1][l,i−1] , [i + 1, r][i+1,r] ；
递归或返回：

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

也就是找到哨兵和k的关系，如果哨兵等于 k+1 ， 那么前面的k个数都是小于哨兵的，因为不需要返回k个数都是有序，所以直接返回前面的k个数。

/**
         * 基于快速排序的数组划分
         *
         * @param arr
         * @param l
         * @param r
         */
public void quickSort(int[] arr, int k, int l, int r) {
    if (l >= r) {
        return;
    }
    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, l, i);    // 交换最后位置
    if (i > k) quickSort(arr, k, l, i - 1); // i > k,表示需要的元素在左数组
    if (i < k)quickSort(arr, k, i + 1, r);  // i < k,表示需要的元素在右数组
    // 相等表示左边就是 k 个元素,而基准此时就是 k + 1，所以直接返回前面k个数
}