剑指offer JZ29 最小的K个数

题目链接：

JZ29 最小的K个数

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果k > 数组的长度，那么返回一个空的数组。

本题思路：

大根堆 实时维护数组的前 k 小值。

首先将前 k 个数插入大根堆中，随后从第 k+1个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入链表返回即可。

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        if(k == 0 || input.length == 0) return new ArrayList<>(); // 避免空指针异常
        
        // PriorityQueue默认小根堆 大根堆需要重写比较器
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1); // queue里元素按从大到小排列
        
        for(int num : input) {
            if(queue.size() < k) { // 将前 k 个数插入大根堆中
                queue.offer(num);
            } else if(queue.peek() > num) {
                queue.poll();
                queue.offer(num); // 放入后自动排序 最大值依旧在队首等待queue.poll();
            }
        }
        
        ArrayList<Integer> list = new ArrayList<>();
        if(k > input.length) return list; // 如果k > 数组的长度 那么返回一个空的链表
        for(int num : queue) {
            list.add(num);
        }
        return list;
    }
}
           

相似题目

leetcode 215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(k == 0 || nums.length == 0) return 0;

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int num : nums) {
            if(queue.size() < k) {
                queue.offer(num);
            } else if(queue.peek() < num) { // 大的留在queue里
                queue.poll();
                queue.offer(num);
            }
        }
        // queue里是最大的k个数 按从小到大排列
        // 从队尾数到队头 队头恰好是第 k 大
        int res = queue.poll(); 
        return res;
    }
}