1. 本题知识点

堆

2. 题目描述

输入 n 个整数，找出其中最小的 K 个数。例如输入 4,5,1,6,2,7,3,8 这 8 个数字，则最小的 4 个数字是 1,2,3,4。

3. 解题思路

建立一个容量为 k 的最大堆的优先队列。遍历一遍元素，如果队列大小 < k，就直接入队，否则，让当前元素与队顶元素相比，如果队顶元素大，则出队，将当前元素入队。

4. 代码

public class Solution {
       public ArrayList
   
     GetLeastNumbers_Solution(int[] input, int k) {
           ArrayList
    
      list = new ArrayList<>();        // k 不能大于数组长度或者小于等于 0        if (k > input.length || k <= 0) {
               return list;        }        // 最大堆        PriorityQueue
     
       priorityQueue = new PriorityQueue<>(Collections.reverseOrder());        // 遍历数组构建最大堆        for (int i : input) {
               // 当最大堆元素个数小于 k 时，直接入队            if (priorityQueue.size() < k) {
                   priorityQueue.offer(i);            } else {
                   // 否则，让当前元素和与根比较，如果如果根大于当前元素，则根出队，当前元素入队                if (priorityQueue.peek() > i) {
                       priorityQueue.poll();                    priorityQueue.offer(i);                }            }        }        // 将最大堆根元素逐个输出        while (priorityQueue.peek() != null) {
               list.add(priorityQueue.poll());        }        // 反转顺序        Collections.reverse(list);        return list;    }}