一道简约而不简单的算法题——数据流的中位数 | 附动画解析

题目描述

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

• void?addNum(int?num)?-?从数据流中添加一个整数到数据结构中。

• double?findMedian()?-?返回目前所有元素的中位数。

示例：

addNum(1)
addNum(2)
findMedian()?->?1.5
addNum(3)?
findMedian()?->?2

输入：

输出：

题目解析

这道题给我们一个数据流，让我们找出中位数。对于数据流这种动态（流动）的数据，如果使用数组存储，那么每次新进来一个数据都进行排序的话，效率很低。

处理动态数据来说一般使用的数据结构是栈、队列、二叉树、堆。

本题中，我们使用?堆?这种数据结构。

首先将数据分为两部分，位于?上边最大堆?的数据要比?下边最小堆?的数据都要小。

为了保证将数据平均分配到两个堆中，在动态的操作的过程中两个堆中数据的数目之差不能超过?1。

为了保证?最大堆中的所有数据都小于最小堆中的数据，在操作过程中，新添加进去的数据需要先和最大堆的最大值或者最小堆中的最小值进行比较。

动画描述

<iframe class="video_iframe rich_pages" data-vidtype="2" data-mpvid="wxv_759937963202641921" data-cover="http%3A%2F%2Fmmbiz.qpic.cn%2Fmmbiz_jpg%2FD67peceibeIR8jmtjOAst2iaEMHt9JELtZNozeoiboALWIszUWozwRFmBnTz42bWBWJHFibwWz1LRBZ6ibVQYvxBIlg%2F0%3Fwx_fmt%3Djpeg" allowfullscreen="" frameborder="0" data-ratio="1.7777777777777777" data-w="1280" scrolling="no" data-src="http://mp.weixin.qq.com/mp/readtemplate?t=pages/video_player_tmpl&auto=0&vid=wxv_759937963202641921" width="352" height="198" data-vh="198" data-vw="352" style="display: none; width: 352px !important; height: 198px !important;"></iframe>播放

代码实现

class?MedianFinder?{
????public?PriorityQueue?minheap,?maxheap;
????public?MedianFinder()?{
????????//维护较大的元素的最小堆
????????maxheap?=?new?PriorityQueue(Collections.reverseOrder());
????????//维护较小元素的最大堆
????????minheap?=?new?PriorityQueue();
????}

????//?Adds?a?number?into?the?data?structure.
????public?void?addNum(int?num)?{
????????maxheap.add(num);
????????minheap.add(maxheap.poll());
????????if?(maxheap.size()?< ?minheap.size())?{
????????????maxheap.add(minheap.poll());
????????}
????}

????//?Returns?the?median?of?current?data?stream
????public?double?findMedian()?{
????????if?(maxheap.size()?==?minheap.size())?{
????????????return?(maxheap.peek()?+?minheap.peek())?*?0.5;
????????}?else?{
????????????return?maxheap.peek();
????????}
????}
};

（本文为AI科技大本营转载文章，转载请联系原作者）

◆
实习生招募
◆