[LeetCode] Find Median from Data Stream

简介: This post shares a very nice solution using two heaps: a max heap for the smaller half and a min heap for the larger half.

This post shares a very nice solution using two heaps: a max heap for the smaller half and a min heap for the larger half. The code is rewritten below in C++, simplifying addNum using the logic in Stefan's post.

class MedianFinder {
public:

    // Adds a number into the data structure.
    void addNum(int num) {
        maxH.push(num);
        int t = maxH.top();
        maxH.pop(); minH.push(t);
        int m = maxH.size(), n = minH.size();
        if (n > m) {
            int t = minH.top();
            minH.pop(); maxH.push(t);
        }
    }

    // Returns the median of current data stream
    double findMedian() { 
        int m = maxH.size(), n = minH.size();
        if (!m && !n) return 0.0;
        if (m == n) return (maxH.top() + minH.top()) / 2.0;
        return (m > n) ? maxH.top() : minH.top();
    }
private:
    priority_queue<int, vector<int>, less<int>> maxH;       // stores the smaller half
    priority_queue<int, vector<int>, greater<int>> minH;    // stores the larger half
};

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

 

目录
相关文章
|
6月前
|
Java
Leetcode 295. Find Median from Data Stream
在一个有序数组中找中位数,但需要支持再数组中添加新的元素。本来是有序里的,可以很轻易就查到中位数,但如果添加新数字后,不一定有序。如果先对数组排序,那代价就比较大了,每次排序时间复杂度O(n*log(n)),看discuss发现了一种很巧妙的解法,可以把添加数据的时间复杂度降低到O(log(n)) ,查询中位数O(1)。
26 0
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
|
JavaScript 索引
LeetCode 436. Find Right Interval
Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.
58 0
LeetCode 436. Find Right Interval
LeetCode 389. Find the Difference
给定两个字符串 s 和 t,它们只包含小写字母。 字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。 请找出在 t 中被添加的字母。
85 0
LeetCode 389. Find the Difference
|
索引
LeetCode 373. Find K Pairs with Smallest Sums
给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。 定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2。 找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。
115 0
LeetCode 373. Find K Pairs with Smallest Sums
|
算法 Python
LeetCode 295. Find Median from Data Stream
中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
65 0
LeetCode 295. Find Median from Data Stream
|
索引
LeetCode 162. Find Peak Element
给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。 数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
75 0
LeetCode 162. Find Peak Element
|
算法 索引 Python
<LeetCode天梯>Day017 字符串中的第一个唯一字符(哈希表+find&rfind) | 初级算法 | Python
<LeetCode天梯>Day017 字符串中的第一个唯一字符(哈希表+find&rfind) | 初级算法 | Python
<LeetCode天梯>Day017 字符串中的第一个唯一字符(哈希表+find&rfind) | 初级算法 | Python
LeetCode之Find the Difference
LeetCode之Find the Difference
98 0