7

以下は、中央値アルゴリズムの中央値を理解しようとする私のコードです (サイズ 5 のブロックを使用)。入力の中央値を取得する方法は理解していますが、中央値が得られるまで入力を繰り返し続けるようにブロックをコーディングする方法がわかりません。次に、その中央値を取得した後、それをピボットとして使用して、役に立たない情報を捨てて入力を分割する方法がわかりません。getMediansArrayサイズ ceil(input.length/5) の配列を返し、配列getMediansから中央値を返します (長さ <= 5 の配列でのみ使用されます)。

public static int[] findKthElement(int[] input, int k) {
    int numOfMedians = (int) Math.ceil(input.length/5.0);
    int[] medians = new int[numOfMedians];
    medians = getMediansArray(input, medians)

    // (1) This only gets the first iteration of medians of the
    // input. How do I recurse on this until I just have one median?

    // (2) how should I partition about the pivot once I get it?
}

public static int[] getMediansArray(int[] input, int[] medians) {
    int numOfMedians = (int) Math.ceil(input.length/5.0);
    int[] five = new int[5];

    for (int i = 0; i < numOfMedians; i++) {
        if (i != numOfMedians - 1) {
            for (int j = 0; j < 5; j++) {
                five[j] = input[(i*5)+j];
            }
            medians[i] = getMedian(five);
        } else {
            int numOfRemainders = input.length % 5;
            int[] remainder = new int[numOfRemainders];
            for (int j = 0; j < numOfRemainders; j++) {
                remainder[j] = input[(i*5)+j];
            }
            medians[i] = getMedian(five);
        }
    }
    return medians;
}

public static int getMedian(int[] input) {
    Arrays.sort(input);
    if (input.length % 2 == 0) {
        return (input[input.length/2] + input[input.length/2 - 1]) / 2;
    }
    return input[input.length/2];
}
4

2 に答える 2

1

中央値の中央値は、基本的にクイック選択アルゴリズム ( http://en.wikipedia.org/wiki/Quickselect ) を改良したものです。クイック選択の平均時間の複雑さは O(n) ですが、トリッキーな入力では O(n^2) まで遅くなる可能性があります。

中央値の中央値を見つけた後に行うことは、クイック選択アルゴリズムの反復に他なりません。中央値の中央値には、常に要素の 30% より大きく、要素の 30% より小さいという優れた特性があります。これにより、ピボットの中央値の中央値を使用したクイック選択が O(n) の最悪の時間の複雑さで実行されることが保証されます。参照: http://en.wikipedia.org/wiki/Median_of_medians

クイック選択を実装することから始めることをお勧めします。これを行うと、クイック選択の各ステップでピボットを選択するために既に必要なコードを使用できます。

于 2015-04-16T17:07:48.670 に答える
0

記憶が正しければ (記憶を更新すると)、Median of Medians はおおよその中央値を選択します。k番目の要素を選択するためにどのように使用できるか理解していません。

于 2015-04-16T16:50:22.980 に答える