最小的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;
    }

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

#笔试题目#
全部评论

相关推荐

评论
点赞
收藏
分享
牛客网
牛客企业服务