java - 获取PriorityQueue中的第K小元素(Java)

Question

为了好玩/Java 练习，我正在做以下问题:

Write a method kthSmallest that takes in a PriorityQueue of integers as input and outputs the k<sup>th</sup> smallest integer. The internal state of the priority queue passed in should not be changed by the method. You may use ONLY one queue or stack as extra data. No other data structures allowed. k is 1-indexed (k = 1 means the smallest value).

获取 k<sup>th</sup>元素很简单:只需删除 k次，因为它是优先队列。我想我可以弹出，将元素放在堆栈上进行存储，然后在完成后将它们添加回队列。但这是行不通的，因为元素在优先级队列中的排序不同。

出于好奇，这是我的代码:

public int kthSmallest(PriorityQueue<Integer> pq, int k) {
    Stack<Integer> s = new Stack<Integer>();

    for (int i = 1; i <= k; ++i) {
            s.push(pq.remove());
    }

    int kthValue = s.peek();

    while (!s.empty()) {
        pq.add(s.pop());
    }

    return kthValue;
}

那么如何在维护优先级队列的内部状态的同时做到这一点呢？

附言- 可以自己查看问题here

Answer 1

您不能保证有关底层状态的任何事情:PriorityQueue 具有的唯一顺序概念是由您在创建它时指定的Comparator 提供的(或其元素的自然顺序)。作为用户，您对此一无所知，并且元素的存储方式应该没有任何区别，只要队列的行为符合基于其规范的预期.