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 个最小的数，你发现有 aMinusIndex 数小于 m，aEqualIndex 等于 m，aPlusIndex 大于 m。

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

（通过查看极端情况很容易看到这一点：假设有零个数小于 m。那么显然你不应该在空数组中搜索任何东西，但因为 0 <= k，你会。）

于 2013-05-06T21:18:32.333 回答
0

我不确切知道你的问题是什么，但你绝对不应该这样做：

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

另外，你不应该做太多的复制，当你这样做时你不会获得任何性能。该算法应该就地完成。

检查这个维基百科：选择算法

于 2013-05-06T21:16:49.070 回答
0

我知道这是家庭作业，因此您的选择可能会受到限制，但我看不出中位数的中位数在这里有何用处。只需使用标准算法对整个数组进行排序，然后选择第 k 个元素。中位数的中位数有助于为排序找到一个非常好的支点。对于 200 长度的数据，您不会节省太多时间。

据我所知，如果不对整个输入数组进行最终排序，就无法准确地获得中位数、百分位数或第 k 个元素。使用子集产生一个估计。如果这是错误的，我真的很想知道，因为我最近正在编写代码以在数百万个数字的数组中查找百分位数！

ps可能是我不完全理解你的代码......

于 2013-05-06T22:24:25.327 回答