从一个不断增长的集合中找到中位数

Question

我在一次面试中遇到了一个有趣的算法问题。我给出了我的答案，但是不确定是否有更好的想法。我欢迎大家写下自己的想法。

你有一个空集合。现在一个接一个地将元素放入集合中。我们假设所有元素都是整数且它们是不同的（根据集合的定义，我们不考虑具有相同值的两个元素）。

每当向集合中添加新元素时，就会询问集合的中位数。中位数的定义与数学中相同：排序列表中的中间元素。这里特别说明一下，当集合大小为偶数时，假设集合大小=2*x，则中位数元素是集合的第x个元素。

一个例子： 从一个空集开始， 当12被添加时，中位数是12， 当7被添加时，中位数是7， 当8被添加时，中位数是8， 当11被添加时，中位数是8， 当5被添加时，中位数是8， 当16被添加时，中位数是8， ……

请注意，首先，元素是逐个添加到集合中的，其次，我们不知道将要添加的元素。

我的答案。

由于这是一个关于寻找中位数的问题，因此需要排序。最简单的解决方案是使用普通数组并保持数组排序。当新元素到来时，使用二分查找找到元素的位置（log_n），然后将元素添加到数组中。由于它是一个普通数组，因此需要移动其余部分的数组，其时间复杂度为n。当插入元素时，我们可以立即获取中位数，使用实例时间。

最坏时间复杂度为：log_n + n + 1。

另一种解决方案是使用链表。使用链表的原因是消除了移动数组的需要。但是找到新元素的位置需要进行线性搜索。添加元素需要瞬间完成，然后我们需要通过遍历数组的一半来找到中位数，这总共需要n/2的时间。

最坏时间复杂度为：n + 1 + n/2。

第三种解决方案是使用二叉搜索树。使用树可以避免数组的移动，但是使用二叉搜索树来查找中位数并不是很理想。因此，我改变了二叉搜索树的方式，使得左子树和右子树始终保持平衡。这意味着在任何时候，左子树和右子树要么具有相同数量的节点，要么右子树比左子树多一个节点。换句话说，确保在任何时候，根元素都是中位数。当然，这需要更改构建树的方式。技术细节类似于旋转红黑树。

如果树被正确地维护，就可以确保最坏时间复杂度为O(n)。

因此，这三个算法对于集合的大小都是线性的。如果不存在亚线性算法，则可以将这三个算法视为最佳解决方案。由于它们之间的差异不大，最好的是最容易实现的第二种方法，即使用链接列表。

因此，我真正想知道的是，是否存在该问题的亚线性算法，如果存在，它会是什么样子。有什么想法吗？

Steve.

- Steve

---

http://zh.wikipedia.org/wiki/自平衡二叉搜索树 我不确定它是否有用于查找中位数，或其复杂度是否低于O（n）。 - Aziz

不清楚问题的确切含义。您是想要插入集合并查找中位数的复杂度，还是仅在各种集合实现中查找中位数？ - Adam Batkin

你的第一个算法就是插入排序。如果你能够用 O(log(n)+n+1) （也就是 O(n)）实现插入排序，我鼓励你发布你的代码... - John Fouhy

在链表的情况下，您不需要进行O(n/2)操作来查找新中位数。新中位数要么与旧中位数相同，要么相邻，因此只需保留对旧中位数的指针并找出哪个是新中位数即可。相同的原则也可以应用于二叉树，尽管步骤的最坏情况是O(log n)。 - Steve Jessop

@Steve 你可以始终缓存中位数值（只需要一个内存槽），这样我们就不必每次想要中位数时都重新计算。未来的查找总是免费的。 - Pacerier

Answer 1

你的复杂度分析很令人困惑。假设总共添加了 n 个项目；我们希望高效地输出 n 个中位数流（其中第 i 个流是前 i 个项目的中位数）。

我认为可以使用两个优先队列（例如二叉或斐波那契堆）在 O(n*lg n) 时间内完成此操作；一个队列用于当前中位数下面的项目（因此最大的元素在顶部），另一个队列用于上面的项目（在这个堆中，最小的元素在底部）。请注意，在斐波那契（和其他）堆中，插入是摊销的 O(1)；只有弹出元素才是 O(lg n)。

这将被称为“在线中位数选择”算法，尽管 Wikipedia 只谈论在线最小/最大值选择。这里有一个 approximate algorithm，以及确定性和近似在线中位数选择的 lower bound（下限意味着不可能有更快的算法！）

如果与 n 相比可能的值很少，你可能可以像排序一样打破基于比较的下限。

- Jonathan Graehl

---

是的，对我之前的表述有些混淆，时间复杂度是针对一次迭代的，也就是添加一个元素并返回当前集合的中位数。时间复杂度并不是指添加n个元素并输出n个中位数的情况。 - Steve

插入是O(1)摊销的；只有弹出一个元素是O(lg n)。不过，您有时必须弹出元素，对吧？因为如果有很多“大”的元素进来，那么之前比中位数大的中等大小的元素最终会变得比中位数小，所以您必须将它们弹出并推到另一个堆上。 - Steve Jessop

是的，绝对没错。这就是为什么我说O(n*lg n)而不是O(n)。无论如何，斐波那契堆对于小规模并不实用；如果我想要O(1)操作，我可能会使用http://www.cs.tau.ac.il/~zwick/papers/meld-talg.pdf。 - Jonathan Graehl

Answer 2

我曾收到同样的面试问题，并想到了 wrang-wrang 的帖子中提出的双堆解决方案。正如他所说，每个操作的时间最坏情况下为 O(log n)。假设输入是随机的，期望时间也是 O(log n)，因为你需要 1/4 的时间“弹出一个元素”。

后来我进一步思考并想出了如何获得恒定的期望时间；事实上，每个元素的期望比较次数变为 2+o(1)。你可以在 http://denenberg.com/omf.pdf 上看到我的文章。

顺便说一句，这里讨论的所有解决方案都需要 O(n) 的空间，因为你必须保存所有的元素。另一种完全不同的方法，只需要 O(log n) 的空间，就可以给你一个中位数的近似值（而非精确的中位数）。很抱歉我不能发布链接（我每篇帖子限制只能有一个链接），但我的论文有指针。

- Larry Denenberg

Answer 3

尽管wrang-wrang已经回答了，但我希望描述一种修改您的二叉搜索树方法的子线性方法。

• 我们使用平衡的二叉搜索树(AVL/红黑等)，但不像您描述的那样超级平衡。因此，添加一个项目是O(log n)
• 对树的一个修改：对于每个节点，我们还存储其子树中的节点数。这不会改变复杂度。(对于一个叶子，这个计数将是1，对于具有两个叶子子节点的节点，这个计数将是3，等等)

现在，我们可以使用这些计数在O(log n)内访问第K小的元素：

def get_kth_item(subtree, k):
  left_size = 0 if subtree.left is None else subtree.left.size
  if k < left_size:
    return get_kth_item(subtree.left, k)
  elif k == left_size:
    return subtree.value
  else: # k > left_size
    return get_kth_item(subtree.right, k-1-left_size)

中位数是Kth最小元素的一种特殊情况（假设你知道集合的大小）。

因此，总体来说，这是另一种O(log n)的解决方案。

- yairchu

Answer 4

我们可以定义一个最小堆和最大堆来存储数字。此外，我们为数字集合定义了一个名为DynamicArray的类，其中包含两个函数：Insert和Getmedian。插入新数字的时间复杂度为O(lgn)，获取中位数的时间复杂度为O(1)。

以下是用C++实现的解决方案：

template<typename T> class DynamicArray
{
public:
    void Insert(T num)
    {
        if(((minHeap.size() + maxHeap.size()) & 1) == 0)
        {
            if(maxHeap.size() > 0 && num < maxHeap[0])
            {
                maxHeap.push_back(num);
                push_heap(maxHeap.begin(), maxHeap.end(), less<T>());

                num = maxHeap[0];

                pop_heap(maxHeap.begin(), maxHeap.end(), less<T>());
                maxHeap.pop_back();
            }

            minHeap.push_back(num);
            push_heap(minHeap.begin(), minHeap.end(), greater<T>());
        }
        else
        {
            if(minHeap.size() > 0 && minHeap[0] < num)
            {
                minHeap.push_back(num);
                push_heap(minHeap.begin(), minHeap.end(), greater<T>());

                num = minHeap[0];

                pop_heap(minHeap.begin(), minHeap.end(), greater<T>());
                minHeap.pop_back();
            }

            maxHeap.push_back(num);
            push_heap(maxHeap.begin(), maxHeap.end(), less<T>());
        }
    }

    int GetMedian()
    {
        int size = minHeap.size() + maxHeap.size();
        if(size == 0)
            throw exception("No numbers are available");

        T median = 0;
        if(size & 1 == 1)
            median = minHeap[0];
        else
            median = (minHeap[0] + maxHeap[0]) / 2;

        return median;
    }

private:
    vector<T> minHeap;
    vector<T> maxHeap;
};

如需更详细的分析，请参考我的博客：http://codercareer.blogspot.com/2012/01/no-30-median-in-stream.html。

- Harry He

---

如果我要计算最后N个元素的中位数而不是所有元素，我该怎么做？ - user877329

Answer 5

1) 与先前的建议一样，保留两个堆并缓存它们各自的大小。左堆保存位于中位数以下的值，右堆保存位于中位数以上的值。如果您只是对右堆中的值取反，那么最小值将位于根部，因此无需创建特殊的数据结构。

2) 当您添加新数字时，可以通过您的两个堆、当前中位数和左右堆的两个根来确定新的中位数，这只需要常数时间。

3) 调用一个私有的线程方法来执行实际的插入和更新工作，但立即返回新的中位数值。您只需要阻塞直到堆根已更新。然后，执行插入的线程只需要在遍历祖父节点时维护锁定；这将确保您可以插入和重新平衡而不会阻止其他正在处理其他子分支的插入线程。

当然，获取中位数变成了一个常数时间过程，现在您可能需要等待同步来自进一步的添加。

罗布

- Rob Leclerc

Answer 6

为了简要解释，您可以通过使每个节点存储其左子树中节点数来高效地增强BST以选择指定秩的键，时间复杂度为O(h)。如果您可以保证树是平衡的，则可以将其减少到O(log(n))。考虑使用AVL（高度平衡）或红黑树（大致平衡），然后您可以在O(log(n))中选择任何键。当您将节点插入或删除AVL时，您可以增加或减少跟踪树中总节点数的变量，以确定中位数的秩，然后可以在O(log(n))中选择它。

- Francesco Gramano

Answer 7

一个带有增强大小(size)字段的平衡树（例如R/B树）在最坏情况下应该能够在对数时间复杂度内找到中位数。我认为这是经典算法教材第14章的内容。

- Fan

Answer 8

为了在线性时间内找到中位数，您可以尝试以下方法（这只是我突然想到的）。每次向集合中添加数字时，您需要存储一些值，并且不需要排序。下面是具体步骤。

typedef struct
{
        int number;
        int lesser;
        int greater;
} record;

int median(record numbers[], int count, int n)
{
        int i;
        int m = VERY_BIG_NUMBER;

        int a, b;

        numbers[count + 1].number = n:
        for (i = 0; i < count + 1; i++)
        {
                if (n < numbers[i].number)
                {
                        numbers[i].lesser++;
                        numbers[count + 1].greater++;
                }
                else
                {
                        numbers[i].greater++;
                        numbers[count + 1].lesser++;
                }
                if (numbers[i].greater - numbers[i].lesser == 0)
                        m = numbers[i].number;
        }

        if (m == VERY_BIG_NUMBER)
        for (i = 0; i < count + 1; i++)
        { 
                if (numbers[i].greater - numbers[i].lesser == -1)
                        a = numbers[i].number;
                if (numbers[i].greater - numbers[i].lesser == 1)
                        b = numbers[i].number;

                m = (a + b) / 2;
        }

        return m;
}

这个程序的作用是，每当你向集合中添加一个数字时，你必须知道有多少“小于你的数字”和有多少“大于你的数字”。因此，如果你有一个数字的“小于”和“大于”相同，这意味着你的数字在集合的正中间，无需对其进行排序。在数字数量为偶数的情况下，你可能有两个选择，所以只需返回这两个数字的平均值即可。顺便说一句，这是C语言代码，希望这能帮助到你。

- nairdaen

---

感谢您提供的代码级描述。据我理解，在median()函数中，numbers是保存集合的数组，n是添加到集合中的新元素，count是添加n之前集合的当前长度，m是中位数。添加一个元素的时间复杂度是线性的。请注意，我们不能假设numbers数组足够大，因此需要检查并可能扩展numbers数组。您的方法不要求数组排序，因此新元素始终可以插入到末尾。但是，您需要进行线性扫描，这比保持数组排序更昂贵。 - Steve

他说他想要亚线性算法。 - yairchu