剑指 Offer 40. 最小的k个数

in with 0 comment

剑指 Offer 40. 最小的k个数

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

先排序,在取出前 k 个数

  1. 快排,以数组第一个元素为基准,头尾指针开始比较大小,头指针在尾指针之前时将比基准大和比基准小的元素调换位置。交换完毕后将头指针和基准调换位置,以基准分隔数组为左右子数组,开始递归左右子数组,退出递归条件:头指针大于尾指针。
  2. 快排优化,因为题目不要求结果排序,所以在拆分数组时必然会在一次拆分钟基准位置 == k 此时即可直接返回 arr 的前 k 个元素,当 k < 基准位置时,结果在左子数组,递归左子树组,反之递归右子数组。

代码

解法一

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

    public void quickSort(int[] arr, int left, int right) {
        if (left > right) return;
        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, j);
        }
        swap(arr, i, left);
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

解法二

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

    int[] quickSort(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, j);
        }
        swap(arr, i, left);
        if (k < i) return quickSort(arr, k, left, i - 1);
        if (k > i) return quickSort(arr, k, i + 1, right);
        return Arrays.copyOf(arr, k);
    }

    void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}