一道简约而不简单的算法题--数据流的中位数

野性酷女 2022-04-24 05:52 94阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

题目来源于 LeetCode 上第 295 号问题：数据流的中位数。难度级别为 Hard，目前通过率为 33.5% 。

### 题目描述 ###

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

例如，

\[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

**输入：**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1] 输入

**输出：**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2] 输出

### 题目解析 ###

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

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

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

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

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

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

### 动画描述 ###

### 代码实现 ###

class MedianFinder {
        
        public PriorityQueue<Integer> minheap, maxheap;
        public MedianFinder() {
        
            //维护较大的元素的最小堆
            maxheap = new PriorityQueue<Integer>(Collections.reverseOrder());
            //维护较小元素的最大堆
            minheap = new PriorityQueue<Integer>();
        }
    
        // 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();
            }
        }
    };

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 1]

[数据结构与算法： 三十张图弄懂「图的两种遍历方式」][Link 2]

[昨天，终于拿到了腾讯 offer][offer]

[几道和「二叉树」有关的算法面试题][Link 3]

[几道和散列（哈希）表有关的面试题][Link 4]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 5]

[几道和「堆栈、队列」有关的面试算法题][Link 6]

[链表算法面试问题？看我就够了！][Link 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

欢迎关注![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: /images/20220218/ad175de08fa448bdb8da8f435e0ac54a.png
[640_wx_fmt_jpeg 1]: /images/20220218/9cab6548b8e54bd497cb1939c99545a1.png
[640_wx_fmt_jpeg 2]: /images/20220218/20d08316840148aca302537b618a8448.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485076&idx=1&sn=ba747d1efd4c009da83681a6bb4ff549&chksm=fa0e6915cd79e003249e9ee045d09a174b0e5aff2a6ecd807e10fd01bfbc1a37da688eb51637&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 3]: /images/20220218/58490cdd6ede49d58cb124301e411fb2.png
[640_wx_fmt_png]: /images/20220218/34859dead58c438cae43fc3612a04531.png