在一个数组中，以最短的时间找到中位数

Question

在一个数组中，以最短的时间找到中位数

10

你有一个数组，比如说 a = { 1,4,5,6,2,23,4,2}; ，现在你需要求出从第二个到第六个位置的中位数（总共是奇数项）。你已经将 a[1] 到 a[5] 存入了另外一个数组 arr[0] 到 arr[4] 中，并对这个新数组进行排序并返回第三个元素 arr[2] 作为中位数。但是这种方法每次都需要将值从一个数组复制到另一个数组，因此初始数组的值不会发生变化。此外，由于使用了排序算法，这种方法需要花费相当长的时间，因此你想知道是否有其他方法可以减少计算时间。你可以搜索相关网站或材料来了解其他方法和实施步骤。

- Sudhanshu Gupta

你是如何对数组进行排序的？ - Evans

我正在使用内置的排序算法。 - Sudhanshu Gupta

6个回答

15

可以在O(n)时间内找到中位数，无需排序；实现这个算法的被称为选择算法。

- Stephen Canon

很棒的回答。只是澄清一下，通常使用的算法（比如在std::nth_element中）期望时间复杂度为O(n)，而非最坏情况下的O(n)。这个问题的最坏情况时间复杂度算法在实践中通常速度较慢。 - Chris A.

更新我的评论。似乎有一些技巧可以实现良好的实际运行时间和 O(n) 的最坏情况运行时间。很想看看哪些实现使用了这些技巧。 - Chris A.

6

如果您正在对同一数组执行多个查询，则可以使用线段树。它们通常用于执行范围最小值/最大值和范围总和查询，但您可以更改它以执行范围中位数。

具有n个区间的段树使用O（n log n）存储，并且可以在O（n log n）时间内构建。范围查询可以在O（log n）时间内完成。

线段树中范围中位数的示例：

您从底部构建线段树（从顶部向下更新）：

                    [5]
        [3]                     [7]
 [1,2]        [4]         [6]         [8] 
1     2     3     4     5     6     7     8

节点涵盖的索引:

                    [4]
        [2]                     [6]
 [0,1]        [3]         [5]         [7] 
0     1     2     3     4     5     6     7

对于4-6范围索引的中位数查询将按以下值路径进行：

                    [4]
                          [5]
0     1     2     3     4     5     6     7

进行中位数的搜索时，您需要知道查询中的总元素数量(3个)以及该范围内的中位数将是第二个元素(索引5)。因此，您实际上在搜索包含该索引的第一个节点，即具有值[1,2]（索引0,1）的节点。

对于范围3-6的中位数搜索要复杂一些，因为您必须搜索两个索引(4,5)，它们恰好位于同一个节点中。

                    [4]
                                [6]
                          [5] 
0     1     2     3     4     5     6     7

线段树

线段树上的区间最小值查询

- Justin

+1，如果在同一个数组上执行多个查询，那么这是正确的方法。 - ffao

@ffao，Justin，你们能详细介绍一下如何在线段树上执行区间中位数查询吗？ - 2147483647

@A.06 我添加了一个区间最小值的示例，但很容易适应于区间中位数。 - Justin

但在范围最小查询中，我们可以找到多个子范围的最小值，并在其中取最小值，但我认为在中位数的情况下不会是这样，因为范围内的中位数不一定是其子范围的中位数的中位数。 - 2147483647

1

@A.06 我已经添加了一个中位数线段树的示例。 - Justin

1

要找到少于9个元素的数组的中位数，我认为最有效的方法是使用像插入排序这样的排序算法。复杂度很差，但对于这么小的数组来说，由于更好的算法（如快速排序）的复杂度中的k，插入排序非常高效。进行自己的基准测试，但我可以告诉你，使用插入排序比使用希尔排序或快速排序获得更好的结果。

- ouah

0

我认为最好的方法是使用中位数算法来计算数组中第k大的元素。您可以在这里找到该算法的整体思路：Java中的中位数，或者在维基百科上查看：http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm，或者浏览互联网。在实现过程中可以进行一些常规改进（在选择特定数组的中位数时避免排序）。但是，请注意，对于少于50个元素的数组，使用插入排序比中位数算法更有效。

- Michal B

0

所有现有的答案在某些情况下都有一些缺点：

对整个子范围进行排序并不是非常高效，因为不需要对整个数组进行排序以获取中位数，并且如果要找到多个子范围中位数，则需要一个额外的数组。
使用 std::nth_element 更有效率，但它仍然会改变子范围，因此仍需要一个额外的数组。
使用线段树可以得到一个高效的解决方案，但需要自己实现该结构或使用第三方库。

出于这个原因，我发布了我的方法，它使用 std::map 并受选择排序算法的启发：

首先将第一个子范围内元素的频率收集到一个 std::map<int, int> 对象中。

有了这个对象，我们可以高效地找到长度为 subrangeLength 的子范围的中位数：

double median(const std::map<int, int> &histogram, int subrangeLength)
{
    const int middle{subrangeLength / 2};
    int count{0};


    /* 我们利用 std::map 中键是排序的这一事实，通过简单迭代并累加频率，就能找到中位数。 */
    if (subrangeLength % 2 == 1) {
        for (const auto &freq : histogram) {
            count += freq.second;
            /* 在子范围长度为奇数时，“middle”是子范围长度除以 2 的下整数界，所以一旦超过它，就找到了中位数。 */
            if (count > middle) {
                return freq.first;
            }
        }
    } else {
        std::optional<double> medLeft;
        for (const auto &freq : histogram) {
            count += freq.second;
            /* 在子范围长度为偶数时，我们需要注意位置在 middle 和 middle + 1 上的元素不同的情况。*/
            if (count == middle) {
                medLeft = freq.first;
            } else if (count > middle) {
                if (!medLeft) {
                    medLeft = freq.first;
                }
                return (*medLeft + freq.first) / 2.0;
            }
        }
    }

    return -1;
}

现在，当我们想要获取下一个子范围的中位数时，我们只需通过减少要删除的元素的频率并为新元素添加/增加它（使用 std::map，这可以在 常数时间 内完成）。现在再次计算中位数，并继续处理所有子范围。

- Marko Popovic

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark · Accepted Answer

使用<algorithm>中的std::nth_element，其时间复杂度为O(N):

nth_element(a, a + size / 2, a + size);
median = a[size/2];