leetcode295. Find Median from Data Stream

microcosm1994 发布于2019-08-15 14:42 / 340人阅读

摘要：思路和代码这里采用了两个优先队列来实现。一个优先队列用来存储字符流中较小的一半，另一个用来存储字符流中数值较大的一半。这样当需要获取当前中位数时，就可以根据当前的数值个数选择一个或是两个数的平均值。

题目要求

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples: 
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.
For example:

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

这里需要我们设计一个数据结构，使得我们可以从当前的字符流中获取中位数。

思路和代码

这里采用了两个优先队列来实现。一个优先队列用来存储字符流中较小的一半，另一个用来存储字符流中数值较大的一半。这样当需要获取当前中位数时，就可以根据当前的数值个数选择一个或是两个数的平均值。

    private PriorityQueue minQueue;
    private PriorityQueue maxQueue;
    /** initialize your data structure here. */
    public MedianFinder () {
        minQueue = new PriorityQueue();
        maxQueue = new PriorityQueue();
    }
    
    public void addNum(int num) {
        maxQueue.add((long)num);
        minQueue.add(-maxQueue.poll());
        if(maxQueue.size() < minQueue.size()){
            maxQueue.add(-minQueue.poll());
        }
        
    }
   
    public double findMedian() {
        if(maxQueue.size() > minQueue.size()){
            return maxQueue.peek();
        }else{
            return ( maxQueue.peek() - minQueue.peek() ) / 2.0;
        }
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 Median Leetcod LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68772.html

[LeetCode]Find Median from Data Stream

Find Median from Data Stream Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Examp...

suemi 2019-08-14 15:08 评论0 收藏0
[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立两个堆，一个堆就是本身，也就是一个最小堆另一个要写一个，使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里，更大的数放在最小堆，较小的数放在最大堆。同时，确保最大堆的比最小堆大，才能从最大堆的顶端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 评论0 收藏0
[Leetcode] Find Median from Data Stream 数据流中位数

摘要：最大堆存的是到目前为止较小的那一半数，最小堆存的是到目前为止较大的那一半数，这样中位数只有可能是堆顶或者堆顶两个数的均值。我们将新数加入堆后，要保证两个堆的大小之差不超过。最大堆堆顶大于新数时，说明新数将处在所有数的下半部分。 Data Stream Median 最新更新：https://yanjia.me/zh/2019/02/... Median is the middle v...

heartFollower 2019-08-14 12:28 评论0 收藏0
480. Sliding Window Median

摘要：题目链接这题和那道比起来多加了个。还是用两个来做，这个操作复杂度用了。和，在保存较小的一半元素，保存较大的一半元素，，注意写的时候不能用，因为可能。没想出来其他方法，参考的解法 480. Sliding Window Median 题目链接：https://leetcode.com/problems... 这题和那道Find Median from Data Stream比起来多加了个...

Scorpion 2019-08-16 10:28 评论0 收藏0
[LintCode/LeetCode] Sliding Window Maximum/Median

摘要：窗口前进，删队首元素保证队列降序加入当前元素下标从开始，每一次循环都将队首元素加入结果数组 Sliding Window Maximum Problem Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration fro...

crelaber 2019-08-14 14:33 评论0 收藏0