题解 | #最小的K个数#

import java.util.*;


public class Solution {
   //sort排序
    // public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
    //     ArrayList<Integer> ret = new ArrayList<>();
    //     if(k==0||k>input.length){
    //         return ret;
    //     }
    //     Arrays.sort(input);
    //     for(int i=0;i<k;i++){
    //         ret.add(input[i]);
    //     }
    //     return ret;
    // }

    //堆排序
    //利用input数组前k个元素创建大顶堆。其余元素与对顶比较，如果小于就加入堆，并且将堆顶弹出(优先级队列会自主排序，将大的都放在前面比较)
    // 最后保证的就是k个最小的
     public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        ArrayList<Integer> ret = new ArrayList<>();
        if(k==0||input.length==0){
            return ret;
        }
        //默认见小根堆
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        //建大根堆
        for(int i=0;i<k;i++){
            q.offer(input[i]);
        }
        //遍历剩下的元素比较
        for(int i=k;i<input.length;i++){
            if(q.peek()>input[i]){
                q.poll();
                q.offer(input[i]);
            }
        }
       //返回结果
       for(int i=0;i<k;i++){
           ret.add(q.poll());
       }
        return ret;
    }
}