题解 | #最小的K个数#

最小的K个数

https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //想到了主持人的那个问题,主持人题目要难一点,除了用最小堆,还要把活动时间进行排序
        //主持人用的是最小堆,默认的就行。它需要先对活动时间进行排序,依次安排最早的活动

        // 实现最大堆,默认的PriorityQueue实现的是最小堆,就是主持人那题用到的
        // 这里面需要实现最大堆,也就是堆顶存放的是最大值,之后把最大值挤掉,留下的就是小的,不用先对数组进行排序
        // 最大堆的实现需要重新定义compare方法
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer a,Integer b){
                return b.compareTo(a);
            }
        });
        for (int i = 0; i < input.length; i++) {
            //把四个最大数字装入堆,然后依次把堆顶让出来
            pq.offer(input[i]);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        //这样堆里面的k个数字就是最小的k个数字了,现在问题就是把堆转换为ArrayList即可
        ArrayList<Integer> res = new ArrayList<>(pq);
        return res;
    }

}

知识点: PriorityQueue 优先级队列,默认是最小堆,最大堆需要重新定义compare方法。

因为要留下最小的数字,把最大的数字依次挤走,所以可以确定本题使用最大堆。

全部评论

相关推荐

coffrar:全都是已读😅沟通一千五百多个了
点赞 评论 收藏
分享
头像
02-26 13:58
门头沟学院 Java
北城_阿亮:把八股背一背,包装一下实习经历项目经历,要是有心思考证就考一考,然后把别人的项目爬到自己github上,包装到简历里,什么三个月?一个月!
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务