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

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

在我所就读的学校里，一位老师向我提出了重新编写查找中位数的方法的挑战，但是不能使用任何数据结构。这包括可以容纳多个值的任何内容，包括字符串、任何形式的数组等。我花费了很长时间来构思，但仍然束手无策。有什么好主意吗？

- jake

---

http://en.wikipedia.org/wiki/Selection_algorithm - Adrian McCarthy

Answer 1

通常用于此任务的算法是Hoare's 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）复杂度。

- Jerry Coffin

---

不清楚问题是否允许对数组进行部分重新排序。请注意，原始解决方案是对数组的副本进行排序，而不是对数组本身进行排序。 - Adrian McCarthy

Answer 2

排序数组并就地进行。像你已经做的那样，取数组中间的元素。不需要额外的存储空间。

这将在Java中花费大约n log n的时间。最好的时间是线性的（你必须至少检查每个元素一次才能确保得到正确的答案）。出于教学目的，额外的复杂度降低并不值得。

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

- Jay Kominek

---

需要引用“没有其他方法可以找到它，而不需要额外的存储空间与输入大小的一半成比例。”我相信我的答案正是如此（尽管速度相对较慢）。 - Adrian McCarthy

耸耸肩，我很乐意放弃我的主张，因为我不在乎，但是我认为你的算法现在并不正确。 - Jay Kominek

Answer 3

一些不是很高效的思路：

对于数组中的每个值，对数组进行一次遍历，计算小于当前值的值的数量。如果该计数是数组长度的“一半”，则您有中位数。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;
    }

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

- Adrian McCarthy

---

我对这个现代的C++东西不是很熟悉，所以也许在编译时出了问题...但是当我询问{5,6,6,6}的中位数时，我得到了1073741826。我将其转换为Racket，那段代码给了我同样的答案。我认为它偏差大约是1073741820？ - Jay Kominek

@Jay Kominek：啊！我错过了一些测试用例。已修复该Bug。如果您发现另一个失败的情况，请告诉我。 - Adrian McCarthy