0

私はコーセラ関連のコースのためにこの宿題をしていて、Java と DS と Algo は初めてです。ここにコード全体を貼り付けることはしません。しかし、以下は、関連するコードで直面している問題です。

したがって、私が使用している中央値PriorityQueueとComparatorインターフェイスを取得するには. PriorityQueue以下の関数から、たとえば 21 個の要素の場合、hLow優先度キューに最小の要素が 11 個あり、hHigh最大の要素が 10 個あるように 2 つの s を作成しようとしています。

public static void addToStream (int k) {
    hLow.add (k);
    if (hLow.size() > (hHigh.size() + 1)) {
        hHigh.add(hLow.poll());
    }
}

私が書いたコンパレータ関数hLowは

hLComp = new Comparator <Integer> () {
        public int compare (Integer o1, Integer o2) {
            return o1.compareTo(o2);
        }   
    };

そして forhHighは

hHComp = new Comparator <Integer> () {
        public int compare (Integer o1, Integer o2) {
            return -o1.compareTo(o2);
        }   
    };

私が直面している問題は、

hHigh.add(hLow.poll())

間違った値を取得します。たとえば、最初の値が 3000 の場合、それは中央値ですが、2 番目の値が入ると、たとえば 6000 になります。次に、コードが if 条件に入り、その後、hHigh.peek3000がhLow.peek表示され、6000 が表示されます。予想。

4

3 に答える 3

1

これは、中央値を見つける例を含むクラス全体です。

public class Median {

    static PriorityQueue<Integer> hHigh  = new PriorityQueue<Integer>(100, 
            new Comparator<Integer>() {
        public int compare (Integer o1, Integer o2) {
            return o1.compareTo(o2);
        }
    });

    static PriorityQueue<Integer> hLow  = new PriorityQueue<Integer>(100, 
            new Comparator<Integer>() {
        public int compare (Integer o1, Integer o2) {
            return -o1.compareTo(o2);
        }
    });

    public static void addToStream (int k) {
        if (hHigh.size() == 0 || k > hHigh.peek()){
            hHigh.add(k);
        }

        else {
            hLow.add(k);
        }

        if (hLow.size() > (hHigh.size() + 1)) {
            hHigh.add(hLow.poll());
        }
        if (hHigh.size() > hLow.size()){
            hLow.add(hHigh.poll()); 
        }
    }

    public static void main(String[] args) {
        addToStream(3104);
        addToStream(6185);
        addToStream(7818);
        addToStream(2106);
        addToStream(5480);
        System.out.println(hLow.peek());
    }
}

このプログラムは次のように出力します: 5480

于 2012-07-26T10:30:35.903 に答える
1

上記の方法はバグがあります。5 4 3 を試してみてください。このアルゴリズムには基本ケースが必要です。ここでよく説明されています：

整数のストリームから移動中央値を見つける

于 2013-04-04T07:47:05.667 に答える
0

各キュー内の値は、コンパレータを実装した方法で並べ替えられます。実装した方法では、関数を追加して、hHigh よりも hLow に配置するだけです。

大きい方の半分を 1 つのキューに保持し、もう一方を 2 番目のキューに保持する場合は、各キューの先頭で値を比較する必要があります。結果に応じて、入力した数値と同様に、キュー間でスワップを行う必要がある場合があります。

追加機能のためにこれを試してください：

まず、hLow コンパレータを hHigh に、またはその逆に割り当てる必要があります。次に、値を追加した後、 hLow.peek() は中央値を提供します。

public static void addToStream (int k) {
    if (hHigh.size() == 0 || k > hHigh.peek()){
        hHigh.add(k);
    }

    else {
        hLow.add(k);
    }

    if (hLow.size() > (hHigh.size() + 1)) {
        hHigh.add(hLow.poll());
    }
    if (hHigh.size() > hLow.size(){
        hLow.add(hHigh.poll()); 
    }
}
于 2012-07-25T22:57:32.030 に答える