2

宿題として、順序付けられていない数の集合から k 番目の順序数を見つけるアルゴリズムを書くように割り当てられました。アプローチとして、アルゴリズムmedian of mediansが提示されています。

残念ながら、私の試みは失敗しました。誰かが間違いを見つけたら、訂正してください。

private int find(int[] A, int size, int k) {
    if (size <= 10) {
        sort(A, 0, size);
        return A[k];
    } else {
        int[] M = new int[size/5];
        for (int i = 0; i < size / 5; i++) {
            sort(A, i*5, (i+1) * 5);
            M[i] = A[i*5 + 2];
        }

        int m = find(M, M.length, M.length / 2);

        int[] aMinus = new int[size];
        int aMinusIndex = 0;
        int[] aEqual = new int[size];
        int aEqualIndex = 0;
        int[] aPlus = new int[size];
        int aPlusIndex = 0;
        for (int j = 0; j < size; j++) {
            if (A[j] < m) {
                aMinus[aMinusIndex++] = A[j];
            } else if (A[j] == m) {
                aEqual[aEqualIndex++] = A[j];
            } else {
                aPlus[aPlusIndex++] = A[j];
            }
        }

        if (aMinusIndex <= k) {
            return find(aMinus, aMinusIndex, k);
        } else if (aMinusIndex + aEqualIndex <= k) {
            return m;
        } else {
            return find(aPlus, aPlusIndex, k - aMinusIndex - aEqualIndex);
        }
    }
}

private void sort(int[] t, int begin, int end) { //simple insertion sort
    for (int i = begin; i < end; i++) {
        int j = i;
        int element = t[i];
        while ((j > begin) && (t[j - 1] > element)) {
            t[j] = t[j - 1];
            j--;
        }
        t[j] = element;
    }
}

私が実行しているテストは、数字 {200, 199, 198, ..., 1) を配置し、順序付けられた配列から最初の数字を取得することです。私は得ています：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -13

return A[k]再帰呼び出しのために、これは行にスローされます:

return find(aPlus, aPlusIndex, k - aMinusIndex - aEqualIndex);
4

3 に答える 3

2

再帰ステップの分岐ロジックは逆です。k 番目に小さい数を見つけようとしていますが、m より小さい aMinusIndex 数、m に等しい aEqualIndex、および m より大きい aPlusIndex があることがわかりました。

aMinusIndex <= k の場合ではなく、aMinusIndex >= k の場合、aMinus で検索する必要があります。

(これは極端な例を見れば簡単にわかります。たとえば、m より小さい数がゼロであるとします。その場合、明らかに、空の配列で何かを検索するべきではありませんが、0 <= k であるため、検索することになります。)

于 2013-05-06T21:18:32.333 に答える
0

あなたの問題が何であるか正確にはわかりませんが、これを行うべきではありません：

sort(A, i*5, (i+1) * 5);

また、あまり多くのコピーを行うべきではありません。それを行うと、パフォーマンスが向上しません。アルゴリズムはその場で行われることになっています。

このウィキペディアを確認してください:選択アルゴリズム

于 2013-05-06T21:16:49.070 に答える