寻找未排序数组的中位数

Question

要找到未排序数组的中位数，我们可以在O（nlogn）时间内为n个元素创建一个最小堆，然后我们可以一次提取n/2个元素，以获取中位数。但这种方法需要O（nlogn）的时间。

我们能否通过某种O（n）时间的方法做到同样的事情呢？ 如果可以，请告诉或建议一些方法。

- Luv

---

可能是重复的问题：如何在O(n)时间内找到长度为n的未排序数组中第k大的元素？（原文链接：https://dev59.com/UnVC5IYBdhLWcg3wjyDu） - Saeed Amiri

请记住，如果时间复杂度为O(nlogn)，那么你可以直接对数组进行排序，并将索引除以2来获得中位数。 - Zombies

建堆所需的时间复杂度为 O(n)，而不是 O(nlogn)。 - GorvGoyl

如果同时拥有所有元素，则构建堆的时间复杂度为O(n)。但是，如果有一系列待处理的元素，则其时间复杂度为O(nlogn)。这就像一个接一个地推入元素，并重复n次。因此，我猜他在这里指的是一系列待处理的元素。 - Raghav Navada

（@GorvGoyl：“逐个提取n/2个元素”需要O(nlogn)的时间。） - greybeard

Answer 1

你可以使用 中位数的中位数算法 在线性时间内找到未排序数组的中位数。

- Sergey Kalinichenko

---

@KevinKostlan 实际上不是近似值，它是真正的中位数，并且可以在线性时间内找到。请注意，在找到中位数的中位数之后（保证大于至少30％的元素并小于至少30％的元素），使用该主元对数组进行分区。然后，如果需要，递归进入其中一个数组，它最多是原始数组大小的70％，以找到真实的中位数（或在一般情况下找到k统计量）。 - dcmm88

@dcmm88：请阅读[https://en.wikipedia.org/wiki/Median_of_medians]。在线性时间内，你能得到的最好猜测是中位数。 （一旦你进行递归，按定义就不再是O(n) /线性了。） - AlanK

在O(n)时间内，您只能找到近似中位数，而不是实际中位数。 - ino

阅读维基百科链接的第一个段落，情况似乎是这样的：中位数算法（它找到每组5个的中位数，然后对这些值进行递归）在线性时间内给出近似中位数，保证位于30%和70%的百分位之间。这可以与QuickSelect（类似于QuickSort，但仅递归地对持有所需元素的部分进行排序）一起使用，在最坏情况下甚至可以在线性时间内找到_确切的中位数_（在任何所需的百分位水平）。因此，这个答案有点正确，但并不是完整的故事。 - Matt

@dcmm88：我得到了一个意外的赞同，被提示阅读你在上面评论中链接的论文。第3页开始，“在N个项目的列表中查找第K大的项的总运行时间为O(nlogn)”（在第2页中间说“不幸的是...查找中位数似乎...比查找第k大的元素要简单得多”）。我想要表达的教训是，投票并不客观，只反映人们的愿望，并不能始终信任它能找到正确的答案。你有什么想法？ - AlanK

Answer 2

我已经点赞了@dasblinkenlight 的答案，因为中位数算法实际上可以在O(n)的时间内解决这个问题。我只想补充一下，使用堆也可以在O(n)的时间内解决这个问题。通过自底向上的方式可以在O(n)的时间内构建堆。请查看以下文章以获取详细说明堆排序

假设你的数组有N个元素，你需要构建两个堆：一个MaxHeap包含前N/2个元素(或(N/2)+1如果N是奇数)，另一个MinHeap包含剩余的元素。如果N是奇数，则中位数是MaxHeap的最大元素(通过获取max来进行O(1)操作)。如果N是偶数，则中位数是(MaxHeap.max()+MinHeap.min())/2，这也需要O(1)的时间。因此，整个操作的真正成本是堆构建操作，其时间复杂度为O(n)。

顺便说一下，当您事先不知道数组元素数量时(例如要为整数流解决相同的问题)，这个MaxHeap/MinHeap算法也可以工作。您可以在以下文章中找到更多有关如何解决这个问题的详细信息整数流的中位数

- rkachach

---

为什么这个方法有效？假设你的数组是[3, 2, 1]。我们会先把前两个数放进一个大根堆：[3, 2]，因此3会成为根节点，所以它的子节点2必须比它小。然后，我们会把[1]放进一个小根堆。按照这个算法，我们会选择大根堆的最大值（根节点）作为中位数。这样难道不会得出3吗？ - Arkidillo

它的时间复杂度是O(n^2)，而不是O(n)。当涉及到算法的大O复杂度时，如果没有指定情况，通常默认指的是最坏情况下的时间复杂度。 - Rick

是的，所给出的答案是错误的。他说需要添加前n/2个元素，这是不正确的。实际上，您必须将前n/2（如果n为奇数，则为n/2 +1）个最小元素添加到Max堆中，其余元素添加到Min堆中，这样可以确保得到正确的答案。请按照他在下面提供的链接“整数流的中位数”进行操作。 - rkscodes

Answer 3

快速选择在O(n)时间内完成，这也被用于快速排序的分区步骤中。

- BrokenGlass

---

我认为快速选择算法不一定在仅一次运行中给出中位数。这取决于您选择的枢轴点。 - Yash

不幸的是，在最坏情况下，使用快速选择查找中位数的时间复杂度将为O(n^2)。这种情况发生在我们在QuickSelect的每次迭代中仅减少1个元素的情况下。考虑一个已经排序好的数组，并且我们总是选择最右边的元素作为枢轴。我知道这样做有点愚蠢，但这就是最坏情况。 - Vishal Sahu

@VishalSahu，你错了。Quickselect的时间复杂度是O(n)，因为它总是选择一个好的枢轴。 - Captain_Obvious

快速选择算法的时间复杂度介于O(n)和O(n^2)之间。 - Pavan Dittakavi

Answer 4

快速选择算法可以在线性时间 (O(n)) 内找到数组中第k小的元素。以下是Python实现：

import random

def partition(L, v):
    smaller = []
    bigger = []
    for val in L:
        if val < v: smaller += [val]
        if val > v: bigger += [val]
    return (smaller, [v], bigger)

def top_k(L, k):
    v = L[random.randrange(len(L))]
    (left, middle, right) = partition(L, v)
    # middle used below (in place of [v]) for clarity
    if len(left) == k:   return left
    if len(left)+1 == k: return left + middle
    if len(left) > k:    return top_k(left, k)
    return left + middle + top_k(right, k - len(left) - len(middle))

def median(L):
    n = len(L)
    l = top_k(L, n / 2 + 1)
    return max(l)

- doizuc

---

这怎么是线性的呢？如果我理解正确，这个实现在最坏情况下的时间复杂度是O(n^2)。 - akki

@akki 因为涉及到随机性，所以它的“期望值”是线性时间。 直觉上来说，随机索引平均会将列表分成1/4大小和3/4大小的两个列表。 - Jacklynn

Answer 5

没有一种O(n)算法可以在任意、未排序的数据集中找到中位数。至少在2022年我所知道的都不行。这里提供的所有答案都是使用堆、中位数、快速选择等的变体/组合，它们严格地是O(nlogn)。

1. 参见https://en.wikipedia.org/wiki/Median_of_medians和http://cs.indstate.edu/~spitla/abstract2.pdf。 2. 问题似乎是关于如何分类算法的混淆，即根据它们的极限（最坏情况）行为进行分类。 "平均"或"通常"是O(n)，而"最坏情况"是O(f(n))，这意味着（按照教科书的说法）"严格是O(f(n))"。例如，快速排序通常被讨论为O(nlogn)（因为它通常表现得像这样），尽管它实际上是一个O(n^2)算法，因为总会有一些病态输入顺序，使其不能比n^2比较更好。

- AlanK

---

@greybeard 感谢您的关注。几周前，我在尝试一门新语言时编写了一个第k大的例程。巧合的是，本周我因为这里的回答得到了一个奖励分数。我添加了一个自发的评论，然后检查了我的事实，然后调整了我的答案（有点强迫症;-)。这是关于算法分类的问题，维基百科在两种情况下都是正确的 - 内省O(nlogn)和Quickselect O(n^2)（在您链接页面的非移动版本上更清晰，顺便提一下，第一个链接已经失效）。目前仍然没有严格的线性解决方案（就我所知）。 - AlanK

好的，关于快速选择变体的维基百科指出：“通过使用更复杂的枢轴策略，可以确保即使在最坏情况下也能实现线性性能；这是在中位数算法中完成的。” 太多不同的事物似乎被标记为introselect，我考虑采用以快速选择样式开始的变体，但仅在监视分区性能并且分区看起来不好时切换到中位数枢轴选择。 - greybeard

@老程序员 在计算昂贵的中心轴时，平均成本作为n（比较）函数的数量级增加，使得平均/典型性能变得更糟。实际上，通常最好使用具有快速中心轴的最坏情况O（n ^ 2）算法，因为遇到最坏情况的概率随着数据集的增大而越来越少。我们是否可以这样说，“目前没有实用的O（n）算法，而且此页面上的答案都是根据大O符号定义（https://en.wikipedia.org/wiki/Big_O_notation）严格为O（nlogn）”？ - AlanK

Answer 6

正如维基百科所说，中位数算法在理论上是O(N)的，但实际上并不常用，因为寻找“好”的枢轴的开销使其变得太慢。
http://en.wikipedia.org/wiki/Selection_algorithm

这里是一个Java源代码，用于查找数组中第k个元素的快速选择算法：

/**
 * Returns position of k'th largest element of sub-list.
 * 
 * @param list list to search, whose sub-list may be shuffled before
 *            returning
 * @param lo first element of sub-list in list
 * @param hi just after last element of sub-list in list
 * @param k
 * @return position of k'th largest element of (possibly shuffled) sub-list.
 */
static int select(double[] list, int lo, int hi, int k) {
    int n = hi - lo;
    if (n < 2)
        return lo;

    double pivot = list[lo + (k * 7919) % n]; // Pick a random pivot

    // Triage list to [<pivot][=pivot][>pivot]
    int nLess = 0, nSame = 0, nMore = 0;
    int lo3 = lo;
    int hi3 = hi;
    while (lo3 < hi3) {
        double e = list[lo3];
        int cmp = compare(e, pivot);
        if (cmp < 0) {
            nLess++;
            lo3++;
        } else if (cmp > 0) {
            swap(list, lo3, --hi3);
            if (nSame > 0)
                swap(list, hi3, hi3 + nSame);
            nMore++;
        } else {
            nSame++;
            swap(list, lo3, --hi3);
        }
    }
    assert (nSame > 0);
    assert (nLess + nSame + nMore == n);
    assert (list[lo + nLess] == pivot);
    assert (list[hi - nMore - 1] == pivot);
    if (k >= n - nMore)
        return select(list, hi - nMore, hi, k - nLess - nSame);
    else if (k < nLess)
        return select(list, lo, lo + nLess, k);
    return lo + k;
}

我没有包含比较和交换方法的源代码，所以很容易将代码更改为使用Object[]而不是double[]。

实际上，您可以预期上述代码的时间复杂度为O(N)。

- Adam Gawne-Cain

Answer 7

问题是：在未排序的数组中找到第K大的元素。

将数组分成n/5组，每组包含5个元素。

现在a1、a2、a3...a(n/5)表示每个组的中位数。

x = 元素a1、a2、.....a(n/5)的中位数。

如果k<n/2，则可以删除中位数大于x的组的最大值、第二大值和第三大值。我们现在可以使用7n/10个元素再次调用函数并找到第k大的值。

否则，如果k>n/2，则可以删除中位数小于x的组的最小值、第二小值和第三小值。我们现在可以使用7n/10个元素再次调用函数，并找到第(k-3n/10)大的值。

时间复杂度分析： T(n)是在大小为n的数组中查找第k大的时间复杂度。

T(n) = T(n/5) + T(7n/10) + O(n)

如果您解决了这个问题，您会发现T(n)实际上是O(n)。

n/5 + 7n/10 = 9n/10 < n

- hrithik maheshw

Answer 8

注意，构建堆实际上需要O(n)而不是O(nlogn)，您可以使用摊销分析或在Youtube上检查此内容。 Extract-Min需要O(logn)，因此提取n/2将花费(nlogn/2) = O(nlogn)的摊销时间。

关于您的问题，您可以简单地查看Median of Medians。

- Tosa Logitech

Answer 9

可以使用Quickselect算法在O(n)内完成，参考第k个顺序统计量（随机算法）。

- Imposter