java - 选择 : Median of medians

Question

作为家庭作业，我被分配编写算法，从无序数字集中找到第 k 个有序数字。作为一种方法，提出了算法中位数的中位数。

不幸的是，我的尝试失败了。如果有人发现错误 - 请纠正我。

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);

Answer 1

递归步骤的分支逻辑是倒退的。您试图找到第 k 个最小的数字，并且发现有 aMinusIndex 数字小于 m，aEqualIndex 等于 m，aPlusIndex 大于 m。

您应该在 aMinus 中搜索 if aMinusIndex >= k，而不是 if aMinusIndex <= k -- 等等。

(通过观察极端情况很容易看出这一点:假设有零个数字小于 m。那么显然你不应该在空数组中搜索任何东西，但因为 0 <= k，你会的。)