不了解中位数算法的中位数来查找第 k 个元素

Question

下面是我的代码，用于尝试理解中位数算法的中位数（使用大小为 5 的块）。我了解如何获取输入的中位数，但我不确定如何对块进行编码以继续递归输入，直到我得到中位数为止。然后在得到那个中位数之后，我不确定如何将它用作一个枢轴来丢弃无用的信息来划分输入。 getMediansArray returns 大小为 ceil(input.length/5) 的数组和 getMedians 只是 returns 数组的中位数（仅用于长度 <= 的数组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];
}

Answer 1

如果我没记错的话 (refreshing my memory) 中位数的中位数 select 是一个 近似值 中位数。我不明白它如何用于 select 第 k 个元素。

Answer 2

Median of medians 基本上只是对 quick-select 算法 (http://en.wikipedia.org/wiki/Quickselect) 的改进。虽然 quick-select 的平均时间复杂度为 O(n)，但对于棘手的输入，它可以减慢到 O(n^2)。

找到中位数的中位数后所做的不过是快速select算法的迭代。中位数的中位数有一个很好的属性，它总是大于 30% 的元素和小于 30% 的元素。这保证了 quick-select 使用中位数的中位数作为主元将运行在 O(n) 的最坏时间复杂度中。参考：http://en.wikipedia.org/wiki/Median_of_medians

我建议您从实施 quick-select 开始。一旦你这样做了，你就可以使用你已经 select 在 quick-select.

的每个步骤中进行调整的代码

不了解中位数算法的中位数来查找第 k 个元素

Not understanding median of medians algorithm to find k-th element

java

arrays

algorithm

median-of-medians