最小的K个数, 问题提问

最小的K个数这道题

题目链接: https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=188&tqId=38279&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high-week%2Fquestion-ranking&tab=answerKey

为什么时间复杂度为nlog(n)的方法比nlog(k)的方法要快呢?

方法1:

将所有元素都添加到堆中, 之后输出前k个, 时间复杂度为nlog(n), 但是提交时间仅为14ms

public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList res = new ArrayList();
        if(input == null || input.length < k || k == 0){
            return res;
        }
        PriorityQueue queue = new PriorityQueue();
        for(int num : input){
            queue.add(num);
        }
        for(int i = 0; i < k ; i++){
            res.add(queue.poll());
        }
        return res;

    }

方法2:

将前k个元素添加到大顶堆中, 接下来把后面的元素依次和堆元素比较, 比堆顶元素小就把堆顶元素去掉, 添加当前元素, 时间复杂度为nlog(k), 但是提交的时间却为90多ms, 经过多次测试的结果, 有大佬可以解释一下为什么嘛?

public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList res = new ArrayList();
        if(input == null || input.length < k || k == 0){
            return res;
        }
        PriorityQueue queue = new PriorityQueue((o1,o2) -> {
            return o2 - o1;
        });
        for(int i = 0; i < input.length ; i++){
            if(i< k){
                queue.add(input[i]);
            }else if( queue.peek() > input[i]){
                Integer temp = queue.poll();
                temp = null;
                queue.add(input[i]);
            }
        }
        for(int i = 0; i < k ; i++){
            res.add(queue.poll());
        }
        return res;
    }

有大佬可以解释一下原因嘛?? 非常感谢

#笔试题目#
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 11:30
找工作7个月,投了7000封,3段世界五百强实习,才有一个offer,牛油们肯定比我强吧
码农索隆:不对不对不对,实习经历这么厉害,简历也没少投,问题出在哪呢
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 12:10
直接上图
牛客13578115...:改得一般,不值80
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务