牛客题霸NC119题解

最小的K个数

牛客题霸NC119

难度：Medium

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

输入

[4,5,1,6,2,7,3,8],4

返回值

[1,2,3,4]

解决思路

使用一个容量为K的最大堆，程序如下：

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

       if(k <= 0 || k > input.length){
           return new ArrayList<>();
       }

        // 大顶堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(
            new Comparator<Integer>(){
                @Override
                public int compare(Integer o1, Integer o2){
                    return o2 - o1;
                }
            }
        );

        for(int m : input){
            if(priorityQueue.size() < k || priorityQueue.peek() > m){
                priorityQueue.offer(m);
            }

            if(priorityQueue.size() > k){
                priorityQueue.poll();
            }
        }

        ArrayList<Integer> list = new ArrayList<>();

        while(!priorityQueue.isEmpty()){
            list.add(priorityQueue.poll());
        }

        return list;

    }
}