题解 | #最小的K个数#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型一维数组 
     * @param k int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        // 核心思想：采用传统堆，至少能够达到O(NlogN)的时间复杂度
        // 至于如何达到O(NlogK)，应当是改进堆，使之仅仅只有K个元素

        // 题解中的方法：先把前K个元素建大根堆，然后往后遍历，若小于堆顶元素，则堆顶出堆，新元素入堆
        // 遍历结束后，这K个元素就是最小的K个元素

        // 0.处理特殊情况
        ArrayList<Integer> result = new ArrayList<>();
        if (k == 0) {
            return result;
        }

        // 1.创建并初始化大根堆，前K个元素入堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 0; i < k; i++) {
            pq.add(input[i]);
        }

        // 2.往后遍历数组，尝试用更小的元素替换掉堆中的最大元素
        for (int i = k; i < input.length; i++) {
            if (input[i] < pq.peek()) {
                // 若当前元素小于堆中最大元素，则弹出最大元素，让当前元素入堆顶替
                pq.poll();
                pq.add(input[i]);
            }
        }

        // 3.此时堆中的k个元素就是所求的k个最小值
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }
        
        return result;
    }
}