我在做练习题实际上，第K个最小

这个问题基本上是你在一个PriorityQueue和一类K正在过去了，你是返回的第k个最小值在那的PriorityQueue。你也对时Queue恢复到其初始状态，并可以使用一个堆栈或队列作为辅助数据结构

This problem is basically you're passed in a PriorityQueue and a certain k, and you are to return the kth smallest value in that PriorityQueue. You are also to restore the PriorityQueue to its initial state and can use one stack or queue as an auxiliary data structure.

我的更高水平的伪想法是，因为时Queue充当最小堆已经从的 Java的PriorityQueue中，我真正需要做的（我的算法）是 从时Queue 1.去除k个元素 2.Store第k个最小值作为局部变量 3.Push删除k个元素到栈（stack这样我就可以以相同的顺序添加元素） 4.Pop从堆栈中的所有元素，并重新将它们添加回时Queue 5.Return第k个最小值

My higher level psuedo thinking is that because the PriorityQueue acts as a min heap already, from Java PriorityQueue, all I really have to do(my algorithm) is 1.Remove k elements from the PriorityQueue 2.Store the kth smallest value as a local variable 3.Push removed k elements onto a Stack(Stack so i can add elements in the same order) 4.Pop all the elements from the Stack and re add them back into the PriorityQueue 5.Return the kth smallest value

下面是code做了这一切

Here is the code to do all of that

public int kthSmallest(PriorityQueue<Integer> pQ, int k) {
    if(k <= 0 || k > pQ.size()) {
           throw new IllegalArgumentException();
    } else {
         Stack<Integer> aux = new Stack<Integer>();
         int kThSmallest = -1;
         for(int c=0;c<k;c++){
               int element = pQ.remove();
               if(c == k-1) 
                   kThSmallest = element;
               aux.push(element);
          }
          while(!aux.isEmpty())
              pQ.add(aux.pop());
         return kThSmallest;
      }

}

当我跑我得到了所有正确的输出，在第k个最小项方案，但我不能恢复我的PriorityQueue的状态。例如，当在一个PriorityQueue传递

When I ran the program I get all the right outputs, in terms of kth smallest, but I can't restore the state of my PriorityQueue. For example, when passed in a PriorityQueue of

[-3, 9, 17, 22, 42, 81] with a k of 3

，我的算法产生正确的结果，17，但它改变时Queue的状态 [ - 3，17，9，81，22，42]

我想过做时Queue的副本，但是违反了一个您可以使用一个堆栈或队列作为辅助数据结构的条件。没有人知道你是怎么去恢复时Queue的状态？

I thought about making a copy of the PriorityQueue but that violate one the conditions that "you can use one stack or queue as an auxiliary data structure". Does anyone know how you go about restoring the state of the PriorityQueue?

推荐答案

有两件事情需要您的实现进行调整。首先，你应该使用一个队列，而不是一个堆栈，如您的辅助数据结构。该项目推到堆栈，然后弹出他们退了出去，将导致在被添加回按相反顺序优先级队列中的 的。如果他们出来的优先级队列为 1，2，3 ，他们将被重新添加到优先级队列为 3，2，1 。这是因为堆栈是一个LIFO（后入先出）数据结构。你想用一个队列为您辅助的数据结构，因为它是一个FIFO（先入先出）的数据结构，所以它会preserve顺序相同。

Two things need to be adjusted in your implementation. First, you should use a queue, rather than a stack, as your auxiliary data structure. The pushing items into a stack and then popping them back out will result in them being added back into your priority queue in reverse order. If they come out of the priority queue as 1, 2, 3, they'll be added back to the priority queue as 3, 2, 1. This is because stacks are a LIFO (Last in, first out) data structure. You want to use a queue as your auxilary data structure because it is a FIFO (First in, first out) data structure, so it will preserve the same order.

二，你只拉第k个元素了先决队列。我建议引流整个队列，所以您要添加的所有元素放回的顺序排队，他们走了出来，而不仅仅是一些。

Second, you only pull the first k elements out of the priorty queue. I would recommend draining the entire queue, so that you're adding all of the elements back into the queue in the order they came out, rather than just some.

换句话说，我想如下调整方案：

In other words, I would adjust your program as follows:

public int kthSmallest(PriorityQueue<Integer> pQ, int k) {
    if(k <= 0 || k > pQ.size()) {
           throw new IllegalArgumentException();
    } else {
         Queue<Integer> aux = new ArrayDeque<Integer>();
         int kThSmallest = -1;
         for(int c=0;c<pQ.size();c++){
               Integer element = pQ.remove();
               if(c == k-1) 
                   kThSmallest = element;
               aux.add(element);
          }
          while(!aux.isEmpty())
              pQ.add(aux.remove());
         return kThSmallest;
      }
}

注意：我在你的程序的类型 INT 改变了元素变量整数。不要紧，你的程序的正确性，但它是一个很好的习惯，要注意自动装箱。泛型类型，如收藏，使用的盒装的整数。这是一个对象，其存储所述原始整数。分配的盒装整数一些类型的 INT 要求，这是装箱，即变回一个 INT 原始。这不是什么大不了的事，但你会立即增加该值回一个集合了。因为你已经装箱到一个原始的 INT ，它需要被装箱回一个整数再次，这要求系统创建一个对象将其存储在因为所有你正在做的值取出来，并把它放回收藏，最好是使用整数的价值在这里，以避免拆箱和拳击的价值，因为它是不是真的需要。

Note: I changed the 'element' variable in your program from type int to Integer. It doesn't matter for the correctness of your program, but it is a good habit to pay attention to auto-boxing. Generic types, like collections, use boxed integers. This is an object that stores the primitive integer. Assigning a boxed integer to something of type int requires that it be unboxed, i.e. turned back into an int primitive. This isn't a big deal, except that you're immediately adding this value back into a collection again. Since you've unboxed it into a primitive int, it needs to be boxed back into an Integer again, and that requires the system to create an object to store it in. Since all you're doing with the value is taking it out of and putting it back into collections, it's better to use an Integer value here, to avoid unboxing and boxing the value, since it isn't really needed.