java - 在 Java 中使用 PriorityQueue 的第 k 个最小数的时间复杂度

Question

我正在尝试解决流行的面试问题在不同整数的数组中找到第 k 个最小的数字。我阅读了一些解决方案，发现堆数据结构非常适合这个问题。

因此，我尝试使用 Collections 框架的 PriorityQueue 类来实现一个解决方案，假设它在功能上与堆相同。

这是我试过的代码:

public static int getKthMinimum(int[] input, int k){
    PriorityQueue<Integer> heap = new PriorityQueue<Integer>();

    // Total cost of building the heap - O(n) or O(n log n) ?
    for(int num : input){
        heap.add(num);      // Add to heap - O(log n)
    }

    // Total cost of removing k smallest elements - O(k log n) < O(n) ?
    while(k > 0){
        heap.poll();        // Remove min - O(log n)
        k--;
    }
    return heap.peek();     // Fetch root - O(1) 
}

基于docs ，轮询和添加方法需要 O(log n) 时间，而 peek 需要常数时间。

1. while 循环的时间复杂度是多少？ (我认为 O(k log n))。
2. 为了这个问题的目的，是否应该将 O(k log n) 视为高于 O(n)？是否有切换的阈值？
3. 这段代码的总时间复杂度是多少？会是 O(n) 吗？
4. 如果不是 O(n)，有没有办法在 O(n) 内解决它，同时使用 PriorityQueue 类？

Answer 1

1. What will be the time complexity of the while loop? (I think O(k log n)).

O(k log n) 是正确的。

2. Should O(k log n) be considered higher than O(n) for the purpose of this question? Is there a threshold where it switches?

你不能假设。 k 可以是 0 到 n−1 之间的任何值，这意味着 k log n 可以是 0 之间的任何值到 n log n。

3. What will be the total time complexity of this code? Will it be O(n)?

O(n log n)，因为这是构建堆的成本。

有可能在 O(n) 时间内构建一个堆，但您的代码不会那样做；如果是这样，您的总复杂度将是 O(n + k log n) 或等价地，< em>O(MAX(n, k log n)).

4. If not already O(n), is there a way to solve it in O(n), while using the PriorityQueue class?

没有。存在selection algorithms在最坏的情况下 O(n) 时间，但它们有点复杂，而且它们不使用 PriorityQueue。

基于 PriorityQueue 的最快解决方案需要 O(MAX(n, n log MIN(< em>k, n−k))) 时间。 (关键是在迭代时只保留堆中的 k 个最小元素 — 或者 n−k 个最大元素并使用最大 -堆，如果 k 足够大，值得这样做。)