3

我正在为有趣/ Java 练习做以下问题：

编写一个方法kthSmallest，将 aPriorityQueue个整数作为输入并输出最小的整数。传入的优先级队列的内部状态不应被该方法更改。您只能使用一个队列或堆栈作为额外数据。不允许其他数据结构。以 1 为索引（表示最小值）。kthkk = 1

获取元素很简单：只需删除时间，因为它是优先级队列。我想我可以直接弹出，将元素放在堆栈上进行存储，然后在完成后将它们添加回队列。但这不起作用，因为元素在优先级队列中的排序方式不同。kthk

这是我的好奇心代码：

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

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

PS - 你可以在这里自己查看问题

4

3 回答 3

2

你不能保证任何关于底层状态的东西：aPriorityQueue拥有的唯一顺序概念是Comparator你在创建它时指定的（或它的元素的自然顺序）。作为用户，您对此一无所知，只要队列的行为符合基于其规范的预期，那么元素的存储方式实际上不应该有任何区别。

于 2013-07-10T00:37:53.147 回答
1

你为什么要卸？无需修改传入的数据结构，这就是您的算法失败的原因。这只不过是一个ITERATOR / VISITOR。您需要做的就是遍历队列并维护一个最小数字的列表/数组。

另请注意，您假设队列中的第 k 个最小整数与优先级中删除的数字相同的假设不一定正确。优先级队列！= 堆。在这种情况下，我可能有一个整数优先级队列，每个整数都有一个优先级字段。

class Node<Integer>
   Integer data;
   int priority;
}

class PriorityQueue {
   List<Node> nodes;

   Integer getHighestPriority() { 
      int maxPriorityIndex = 0;
      for(int i=0; i< nodes.size(); i++) {
      if(n.priority > maxPriority) {
           maxPriorityIndex = nodes.get(i);
      }
      return nodes.get(maxPriorityIndex);
   }
}
于 2013-07-10T01:00:43.937 回答
0

已经说明了很多提示，我会保持简短的回答：

您正在处理来自给定对象的方法调用，而您对此一无所知。您不知道是否使用了一个奇怪的比较器来比较队列中的整数（例如，一个比较器表示所有事物都是平等的，并且总是返回 0）。这就是为什么你在任何情况下都不应该修改给定的对象（就像你对 poll/add 所做的那样）。

在这种情况下，要解决此问题，您可以使用缓冲区对象（如问题中所述，队列或堆栈（我使用了给定的队列）来使用您选择的比较器并通过添加给定的比较器来缓冲它队列到缓冲区对象。

我在 pastebin 的解决方案，因为我没有任何剧透标签:-(

于 2013-07-10T01:57:57.393 回答