使用堆的Kth最小的时间复杂度

Question

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

根据我的理解，你首先要通过整个数组，即O（n）填充你的堆。而且，当你到达数组的末尾时，你会在堆顶部有第k个最小的元素，你可以立即返回作为最终答案。

但是，在下面的代码中，有一个从k开始到数组长度的附加循环。我并不真正了解这个第二循环的需要。

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(); 
} 

Answer 1

您读错代码，它应该是：

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

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

在当前时刻，最小K.peek（）将保持当前最小的K.

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