Description

剑指 Offer 40. 最小的k个数
难度简单167
输入整数数组 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

    Solution

    利用快速排序，每一轮 partition 分区的时候，得到 partition 返回的分区点 v，对比分区点 v 与 k 是否相同，相同则 [0 - v] 为最小的 k 个数，不同则继续排序查找

    1. class Solution {
    2.   public int[] getLeastNumbers(int[] arr, int k) {
    3.       int target = quickSortToSeekMinNums(arr, 0, arr.length-1, k);
    4.       return  Arrays.copyOf(arr, k);
    5.   }
    6.   private int quickSortToSeekMinNums(int[] nums, int lo, int hi, int k){
    7.       if (lo >= hi)  // 快速排序递归结束
    8.           return lo;
    9.       int v = partition(nums, lo, hi);
    10.       if ( (v + 1) == k)  // 分区点 v + 1 与 k 相同的情况 
    11.           return v;
    12.       else if ( (v + 1) < k)        // 分区点 v + 1 小于 k，说明右边还包含最小 k 个数，向右边排序查找
    13.           return quickSortToSeekMinNums(nums, v + 1, hi , k);
    14.       else  // 分区点 v + 1 大于 k，向左边排序查找
    15.           return quickSortToSeekMinNums(nums, lo, v - 1, k );
    17.   }
    19.   public int partition(int[] nums, int lo, int hi){
    20.       int v = nums[lo];
    21.       int i = lo + 1, j = hi;
    22.       while (i <= j){
    23.           if (nums[i] <= v){
    24.               i ++;
    25.               continue;
    26.           }
    27.           swap(nums, i, j --);
    28.       }
    29.       swap(nums, lo, j);
    30.       return j;
    31.  }
    32.   private void swap(int[] nums, int i, int j){
    33.       int temp = nums[i];
    34.       nums[i] = nums[j];
    35.       nums[j] = temp;
    36.   }
    37. }

    执行结果：通过
    显示详情
    执行用时：3 ms, 在所有 Java 提交中击败了81.58%的用户
    内存消耗：39.8 MB, 在所有 Java 提交中击败了72.58%的用户

Solution 2

PriorityQueue 默认是小顶堆

使用优先队列 PriorityQueue 存储所有的数，依次取出 k 个数，此 k 个数就是 最小的 k 个数

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> minNums = new PriorityQueue<>();
        for (int num : arr){
            minNums.add(num);
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i ++)
            res[i] = minNums.poll();
        return res; 
    }
}

执行结果：通过
显示详情
执行用时：19 ms, 在所有 Java 提交中击败了31.34%的用户
内存消耗：39.6 MB, 在所有 Java 提交中击败了89.85%的用户

优先队列的第二种实现，将 PriorityQueue 转成大顶堆的实现方式，PriorityQueue 中保存最小的 k 个数

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if ( k == 0 || arr.length == 0)
            return new int[0];
        // PriorityQueue 默认是小顶堆
        PriorityQueue<Integer> minNums = new PriorityQueue<>(k, (x,y) -> y - x );
        for (int num : arr){
            if (minNums.size() < k)
                minNums.add(num);
            else if (num <= minNums.peek()){
                minNums.poll();
                minNums.add(num);
            }
        }
        int[] res = new int[k];
        int index = 0;
        for (int num : minNums)
            res[index++] = num;

        return res;
    }
}

执行结果：通过
显示详情
执行用时：12 ms, 在所有 Java 提交中击败了41.92%的用户
内存消耗：40.2 MB, 在所有 Java 提交中击败了31.45%的用户