从增长集中查找中值

您的复杂性分析令人困惑。假设添加了n个项总数;我们希望高效地输出n个中间值的流(其中流中的i是前i个项的中间值)。

我相信这可以在O(n*lg n)时间内使用两个优先级队列(例如二进制或斐波那契堆)来完成;一个队列用于当前中位数以下的项(因此最大的元素位于顶部),另一个队列用于其上的项(在此堆中,最小的元素位于底部)。请注意,在fibonacci(和其他)堆中,插入是O(1)摊销的;它只是弹出一个O(lg n)元素。

这将被称为“在线中值选择”算法,尽管 Wikipedia 只讨论在线最小/最大选择。这里有一个 approximate algorithm 和A lower bound 关于确定性和近似在线中值选择(下限意味着不可能有更快的算法!)

如果与n相比可能有少量的值,则可以像排序那样打破基于比较的下限。

我收到了同样的采访问题,并在WrangWrang的帖子中提出了两个堆解决方案。正如他所说,每次操作的时间是O(log n)最坏的情况。这个 预期 时间也是O(log n),因为您必须“弹出一个元素”1/4的时间假设为随机输入。

随后我进一步考虑了一下,并找出了如何获得恒定的预期时间;实际上,每个元素的预期比较数变为2+o(1)。你可以在看到我写的 http://denenberg.com/omf.pdf .

顺便说一句,这里讨论的解决方案都需要空间o(n),因为您必须保存所有元素。一个完全不同的方法,只需要O(log n)空间,就可以得到中值的近似值(而不是确切的中值)。很抱歉,我不能发布链接(每个帖子只能有一个链接),但我的论文有指针。

虽然wrang wrang已经回答了这个问题,但是我想描述一下对二叉搜索树方法的一个修改,它是次线性的。

• 我们使用一个平衡的二进制搜索树(avl/red-black/etc),但不像您描述的那样是超平衡的。所以添加一个项目是o(log n)
• 对树进行一次修改:对于每个节点,我们还将节点的数量存储在其子树中。这不会改变复杂性。(对于一个叶,此计数为1,对于具有两个叶子节点的节点,此计数为3,依此类推)

我们现在可以使用这些计数访问o(log n)中的kth最小元素:

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)解决方案。

我们可以定义最小和最大堆来存储数字。此外,我们还为数字集定义了一个类dynamiccarray,它有两个函数: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 .

1)和前面的建议一样,保留两个堆并缓存它们各自的大小。左堆将值保持在中间值以下,右堆将值保持在中间值以上。如果只对右堆中的值求反,那么最小的值将位于根目录,因此不需要创建特殊的数据结构。

2)当您添加一个新的数字时,您可以根据两个堆的大小(当前的中值和L&R堆的两个根)来确定新的中值,这只需要持续的时间。

3)调用私有线程方法执行实际工作以执行插入和更新,但立即返回新的中间值。您只需要阻塞,直到堆根被更新。然后,执行插入操作的线程在遍历树时只需要在遍历祖父母节点上保持一个锁;这将确保您可以插入并重新平衡,而不会阻塞在其他子分支上工作的其他插入线程。

获取中间值变成了一个固定的时间过程,当然,现在您可能需要等待进一步添加的同步。

抢劫

平衡树(例如R/B树),具有扩充的 大小 在最坏的情况下,字段应找到lg(n)时间的中位数。我想它在经典算法课本的第14章。

为了使解释简短,您可以通过让每个节点在其左子树中存储节点数,有效地扩充BST,以选择O(H)中指定列组的键。如果你能保证树是平衡的,你可以把它减少到O(log(n))。考虑使用高度平衡的AVL(或大致平衡的红黑树),然后可以在O(log(n))中选择任何键。当您在AVL中插入或删除一个节点时,您可以增加或减少一个变量,该变量跟踪树中的节点总数,以确定中位数的排名,然后您可以在O(log(n))中进行选择。

为了找到线性时间的中位数,你可以试试这个(我刚想到)。每次向集合中添加数字时,都需要存储一些值,而不需要排序。在这里。

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代码,我希望这有帮助。