使用堆最小Kth的时间复杂度 [英] Time complexity of Kth smallest using Heap

问题描述

以下是使用堆在数组中查找第k个最小元素的代码.时间复杂度为O(n log(k))，其中k是堆的大小.

Following is a code for finding the kth smallest element in an array using heap. The time complexity is O(n log(k)) where k is the size of the heap.

根据我的理解，您首先要遍历整个数组，即O(n)来填充您的堆.而且，当您到达数组的末尾时，您将在堆的顶部拥有第k个最小的元素，您可以立即将其返回作为最终答案.

As per my understanding, you first go through the entire array i.e. O(n) to populate your heap. And, when you reach the end of the array, you would have the kth smallest element at the top of the heap that you can instantly return as the final answer.

但是，在下面的代码中，还有一个附加循环，从k开始到数组的长度.我不太了解第二个循环的必要性.

However, in the code below, there is an additional loop starting from k to the length of the array. I'm not really understanding the need for this second loop.

public int findKthSmallest(int[] arr, int k ) {

    if(k <= 0 || k > arr.length) {
        throw new IllegalArgumentException();
    }

    PriorityQueue<Integer> smallestK = new PriorityQueue<>(k, Collections.reverseOrder());

    for(int i = 0; i < arr.length; i++) {
        smallestK.add(arr[i]);
    }

    for(int j = k; j < arr.length; j++) {
        if(arr[j] < smallestK.peek()) {
            smallestK.remove();
            smallestK.add(arr[j]);
        }
    }
    return smallestK.peek();
}

推荐答案

您读错了代码，应该是:

You read the wrong code, it should be:

for(int i = 0; i < k; i++) {
    smallestK.add(arr[i]);
}

在第一个循环中，我们需要在堆中插入第一个k元素.

In the first loop we need to insert the first k element in heap.

当前时刻，smallestK.peek()将保存当前的最小K.

At current moment, smallestK.peek() will hold the current smallestK.

在第二个循环中，我们处理数组中的剩余元素.我们将该值与当前的最小K进行比较.

In the second loop, we process the remaining element in array. We compare the value with the current smallestK.

这篇关于使用堆最小Kth的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！