0

早急に助けが必要です。キューから削除せずに、すべてのオブジェクトの中で中央値を持つオブジェクトを調べる peekMedian 関数を実装したいと考えています。( size/2 + 1) 番目に低い値を持つオブジェクトを返す必要があります。

たとえば。キューに次の値があるとします。{ 2, 1, 2, 2, 6, 4, 2, 5} の場合、メソッドは 2 を返す必要があり、オブジェクトは削除されません。

collection.sort()を使用してみましたが、質問に従ってキューをソートするべきではありません。また、キュー要素を配列にコピーし、n 番目に低い値を見つけて値を返すことも試みました。しかし、質問は「オブジェクトを返す」と言います。.. また、ソリューションの複雑さを軽減する必要があります。

4

3 に答える 3

0

これを試して 

        import java.util.ArrayDeque;
        import java.util.Iterator;

        public class ArrayDequeDemo {
           public static void main(String[] args) {

        ArrayDeque<Integer> que = new ArrayDeque<Integer>();
            // add elements in queue
              que.add(2);
             que.add(1);
              que.add(2);
              que.add(2);
              que.add(6);
              que.add(4);
              que.add(2);
              que.add(5);

    Integer median = peekMedian(que);

     System.out.println(median);
       }


  private static Integer peekMedian(ArrayDeque<Integer> que){

    Integer ele=0;      //required number
   int size=que.size();  

   //finding the index of ele.
   int elementFromlastIndex= (size/2)+1;


   Iterator descItr = que.descendingIterator();

    int counter=0;  


// iterate in reverse order  till the index of ele is not reached.The loop will break when  when index of ele is reached and thereby finding required element. 

    while(descItr.hasNext() && counter!=elementFromlastIndex) {
             ele =( Integer)descItr.next();
            ++counter;

         if(counter==elementFromlastIndex)
          break;
}//while  
      return ele;       

   }
   }  
        }//class
于 2012-08-24T21:43:13.393 に答える
0

やり方はわかったと思いきや、昨日実装を依頼されました。

O(1) 時間で max または min を実装するのは簡単ですね。キューを 2 つのキューに分割し、1 つには中央値よりも小さいアイテムを格納し、もう 1 つには中央値よりも大きいアイテムを格納し、常にこの関係を維持し、アイテムを挿入するときは、各キューに順番に挿入してください。中央値。

関係を維持するときに何らかの操作があるかもしれませんが、O(1) で最大値または最小値を取得し、O(1) でインセットを下げることができるため、完全に O(1) 時間になると思います。したがって、それはまだ O(1) です。 、 いいですね。

私が正しかったことを願っています。何か問題がある場合は、教えてください。

于 2012-09-18T17:05:22.087 に答える
0

これは宿題のように見えるので、問題を解決するアルゴリズムを投稿します。

  1. オブジェクトの補助コレクションとして役立つ新しいキューを作成します。
  2. 初期キューからのオブジェクトのデキューを開始し、それらを補助キューにキューイングします。
  3. キューの元のサイズがわかっている場合は、(size/2 + 1)n 番目の要素に到達したときに、補助オブジェクトを使用してその値のコピーを保持します。
  4. ステップ 2 のプロセスを続行します。
  5. 可能であれば、キューを補助キューに置き換えます。それ以外の場合は、補助キューから元のキューへのパス 2 のプロセスを繰り返します。
  6. 中央値の値を持つ補助オブジェクトを返します。

ところで、あなたは中央値の概念が違うと思います。あるいは、それが問題の提案方法なのかもしれません。

注: 割り当てがキュー内のオブジェクトを削除せずにこれを行う場合、少なくともキューを配列または LinkedList として脅し、それを反復処理することは不可能です。

Java Queue を使用したコードの実装を紹介します。

public <T> T peekMedian(Queue<T> queue) {
    int medianIndex = queue.size() / 2 + 1; //based on your question.
    Queue<T> auxQueue = new LinkedList<T>();
    T result;
    int count = 1;
    while(queue.peek() != null) {
        auxQueue.add(queue.pop());
        if (count == medianIndex) {
            result = auxQueue.peek();
        }
        count++;
    }
    while(auxQueue.peek() != null) {
        queue.add(auxQueue.pop());
    }
    return result;
}
于 2012-08-24T20:14:48.960 に答える