[LeetCode]Find Median from Data Stream

suemi 发布于2019-08-14 15:08 / 1065人阅读

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.
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:
add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2

分析

这道题的经典做法就是维护两个Heap, 一个MaxHeap, 一个MinHeap，维护他们的size，比如保证

MaxHeap.size() - MinHeap.size() >= 1

当然这种题可以有些follow up, 比如：

除了heap做，还有什么其他方法？
BST可以，比如可以在Node里增加一个size表示整个children的数量，findMedian时间复杂度会增加到log(n);

如果是找比如处在1/10th的元素，怎么找？
同样可以用两个heap做，维护一个的size是另一个size的1/9即可。

复杂度

time: addNum -> O(log(n)), findMedian -> O(1)
space: O(n)

代码

class MedianFinder {

    // Adds a number into the data structure.
    PriorityQueue minHeap = new PriorityQueue();
    PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder());
    
    public void addNum(int num) {
        maxHeap.add(num);
        minHeap.add(maxHeap.remove());
        
        // 维护两个heap的size 
        if (minHeap.size() > maxHeap.size()) 
            maxHeap.add(minHeap.remove());
    }

    // Returns the median of current data stream
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) 
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        else 
            return maxHeap.peek();
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();

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

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

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

leetcode295. Find Median from Data Stream

摘要：思路和代码这里采用了两个优先队列来实现。一个优先队列用来存储字符流中较小的一半，另一个用来存储字符流中数值较大的一半。这样当需要获取当前中位数时，就可以根据当前的数值个数选择一个或是两个数的平均值。题目要求 Median is the middle value in an ordered integer list. If the size of the list is even, t...

microcosm1994 2019-08-15 14:42 评论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