3

私は楽しい/ Javaの練習のために次の問題をやっています:

kthSmallest整数の aを入力として受け取り、最小PriorityQueueの整数を出力するメソッドを作成します。渡されたプライオリティ キューの内部状態は、メソッドによって変更されるべきではありません。追加データとして使用できるキューまたはスタックは 1 つだけです。他のデータ構造は許可されていません。は 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 に答える