剑指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]

限制：

• 0 <= k <= arr.length <= 10000
• 0 <= arr[i] <= 10000

思路 1：利用堆(Java->优先队列)

• 保证堆的大小为k ，然后遍历数组中的数字，遍历的过程做如下判断
  • 1. 若目前堆中的大小小于 K , 那么将当前的数字加入堆中
  • 2. 否则 判断当前数字与大顶堆堆顶元素的大小关系，如果当前数字比大顶堆堆顶还大，这个数字就直接跳过
    3. 反之，如果当前数字比大顶堆堆顶小，先poll掉堆顶，再将该数字放入堆中

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }

        //默认是小根堆，实现大根堆需要重写一下比较器
        Queue<Integer> pq = new PriorityQueue<>((v1,v2) -> v2 - v1);
        for(int num:arr){
            if(pq.size() < k){
                pq.offer(num);
            }else if (num < pq.peek()){
                pq.poll();
                pq.offer(num);
            }
        }

        //返回堆中元素
        int[] res = new int[pq.size()];
        int idx = 0;
        for(int num:pq){
            res[idx++] = num;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度 ： O(N LogK)

  • 遍历一遍数组的开销O(N) + 堆插入的开销（Ologk）

• 空间复杂度 ：O(k)

  • 使用了大小为k 的堆

另外几种解法 ： 待学习

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/

1. 二叉排序树
2. 快速排序

打赏