BM46_题解 | #最小的K个数#

解题思路：

1、关键用到了PriorityQueue，最大堆，这是我日常编程中没有用到的数据结构。

具体步骤：

1、最大堆录入input数组的前k个元素。

2、再用这个堆不断跟input数组剩下的 n-1-k个元素对比。

3、转堆成list返回结果

import java.util.*;


public class Solution {
    /**
     * @param input int整型一维数组 
     * @param k int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {  
       ArrayList<Integer> res =  new ArrayList<Integer>();
        if(k > input.length || k==0 ) {
            return res;
        }
        
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2)->o2.compareTo((o1))); 
        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]);
            }
        }

        while(!q.isEmpty()) {
            res.add(q.poll());
        }
        return res;
    }
}