剑指offer-29-最小k个数

思路

堆维护一个有序序列（优先级队列），size()=k
注意处理k==0或者k<input.length

代码

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(input.length<k || k==0){return new ArrayList<Integer>();}
        PriorityQueue<Integer> heap=new PriorityQueue<>((o1,o2)->Integer.compare(o2,o1));
        for(int i=0;i<input.length;i++){
            if(heap.size()<k){
                heap.add(input[i]);
            }else{
                if(heap.peek()>input[i]){
                    heap.poll();
                    heap.add(input[i]);
                }
            }
        }
        return new ArrayList<Integer>(heap);
    }
}