JZ40 最小的K个数

JZ40 最小的K个数

最小的K个数_牛客题霸_牛客网 (nowcoder.com)

NC119 最小的K个数

最小的K个数_牛客题霸_牛客网 (nowcoder.com)

---

// //Arrays.sort
// import java.util.*;
// public class Solution {
//     public ArrayList<Integer> GetLeastNumbers_Solution(int [] array, int k) {
//         ArrayList<Integer> ret=new ArrayList<>();
//         if(array==null||array.length==0||k==0||k>array.length){
//             return ret;
//         }
//         Arrays.sort(array);
//         for(int i=0;i<k;i++){
//             ret.add(array[i]);
//         }
//         return ret;
//     }
// }


//堆-优先级队列-最小的k个数-建大堆
//PriorityQueue默认为小堆,建大堆需要调用Collections.reverseOrder()
import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] array, int k) {
        ArrayList<Integer> ret=new ArrayList<>();
        if(array==null||array.length==0||k==0||k>array.length){
            return ret;
        }
        PriorityQueue<Integer> pq=new PriorityQueue<>(k,Collections.reverseOrder());
        for(int i=0;i<k;i++){
            pq.offer(array[i]);
        }
        for(int i=k;i<array.length;i++){
            if(array[i]<pq.peek()){
                pq.poll();
                pq.offer(array[i]);
            }
        }
        for(int i=0;i<k;i++){
            ret.add(pq.poll());
        }
        return ret;
    }
}