在没有数据结构的情况下寻找中位数

Question

（我的代码是用Java写的，但问题是不可知的；我只是在寻找算法思路）

所以问题来了：我做了一个简单地找到数据集的中位数的方法（以数组的形式给出）。这是实现：

public static double getMedian(int[] numset) {
    ArrayList<Integer> anumset = new ArrayList<Integer>();
    for(int num : numset) {
        anumset.add(num);
    }
    anumset.sort(null);

    if(anumset.size() % 2 == 0) {
        return anumset.get(anumset.size() / 2);
    } else {
        return (anumset.get(anumset.size() / 2)
                   + anumset.get((anumset.size() / 2) + 1)) / 2;
    }
}

然后我去的学校的一位老师挑战我写一个方法来再次找到中位数，但不使用任何数据结构。这包括任何可以容纳多个值的东西，因此包括字符串、任何形式的数组等。我花了很长时间试图构思一个想法，但我被难住了。有什么想法吗？

Answer 1

Sort数组到位。像您已经在做的那样获取数组中间的元素。不需要额外的存储空间。

这将花费 n log n 左右的时间 Java。最佳可能时间是线性的（您必须至少检查每个元素一次以确保获得正确答案）。出于教学目的，额外降低复杂性是不值得的。

如果您不能就地修改数组，则必须以显着的额外时间复杂度为代价，以避免使用与输入大小的一半成比例的额外存储。（如果你愿意接受近似值，事实并非如此。）

Answer 2

一些不是很有效的想法：

对于数组中的每个值，通过数组计算低于当前值的值的数量。如果该计数是 "half" 数组的长度，则您有中位数。 O(n^2)（需要一些思考才能弄清楚如何处理中值的重复项。）

您可以通过跟踪到目前为止的最小值和最大值来稍微提高性能。例如，如果您已经确定 50 太高而不能成为中位数，那么您可以跳过对每个大于或等于 50 的值的数组计数。同样，如果您已经确定 25太低，您可以跳过每个小于或等于 25 的值的计数过程。

在 C++ 中：

    int Median(const std::vector<int> &values) {
        assert(!values.empty());
        const std::size_t half = values.size() / 2;
        int min = *std::min_element(values.begin(), values.end());
        int max = *std::max_element(values.begin(), values.end());
        for (auto candidate : values) {
            if (min <= candidate && candidate <= max) {
                const std::size_t count =
                    std::count_if(values.begin(), values.end(), [&](int x)
                                    { return x < candidate; });
                if (count == half)     return candidate;
                else if (count > half) max = candidate;
                else                   min = candidate;
            }
        }
        return min + (max - min) / 2;
    }

糟糕的性能，但它不使用数据结构，也不修改输入数组。

Answer 3

该任务的常用算法是 Hoare 的 Select 算法。这很像快速排序，除了在快速排序中你递归排序 both 分区后，但对于 select 你只在包含该项目的分区中进行递归调用感兴趣。

例如，让我们考虑这样的输入，我们将在其中找到第四个元素：

[7、1、17、21、3、12、0、5]

我们将任意使用第一个元素 (7) 作为我们的支点。我们最初将其拆分为（用 *:

标记的枢轴

[ 1, 3, 0, 5, ] *7, [ 17, 21, 12]

我们正在寻找第四个元素，而 7 是第五个元素，因此我们（仅）对左侧进行分区。我们将再次使用第一个元素作为我们的支点，给出（使用 { 和 } 来标记我们现在忽略的输入部分）。

[ 0 ] 1 [ 3, 5 ] { 7, 17, 21, 12 }

1 已作为第二个元素结束，因此我们需要将其右侧的项（3 和 5）进行分区：

{0, 1} 3 [5] {7, 17, 21, 12}

使用 3 作为主元元素，我们最终左边什么都没有，右边 5。 3是第三个元素，所以我们要向右看。这只是一个元素，因此 (5) 是我们的中位数。

通过忽略未使用的一侧，这将用于排序的复杂度从 O(n log n) 降低到仅 O(N) [尽管我有点滥用符号——在这种情况下我们正在处理预期的行为，而不是最坏的情况，就像 big-O 通常那样。

如果你想确保良好的行为（以平均速度稍慢为代价），还有中位数算法。

这保证了 O(N) 复杂度。

在没有数据结构的情况下寻找中位数

Finding Median WITHOUT Data Structures

language-agnostic

median