[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();

 

目录
相关文章
|
11月前
|
Java
Leetcode 295. Find Median from Data Stream
在一个有序数组中找中位数,但需要支持再数组中添加新的元素。本来是有序里的,可以很轻易就查到中位数,但如果添加新数字后,不一定有序。如果先对数组排序,那代价就比较大了,每次排序时间复杂度O(n*log(n)),看discuss发现了一种很巧妙的解法,可以把添加数据的时间复杂度降低到O(log(n)) ,查询中位数O(1)。
49 0
|
11月前
Leetcode Find Minimum in Rotated Sorted Array 题解
对一个有序数组翻转, 就是随机取前K个数,移动到数组的后面,然后让你找出最小的那个数,注意,K有可能是0,也就是没有翻转。
44 0
|
算法 Python
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
|
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.
81 0
LeetCode 436. Find Right Interval
LeetCode 389. Find the Difference
给定两个字符串 s 和 t,它们只包含小写字母。 字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。 请找出在 t 中被添加的字母。
114 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)。
157 0
LeetCode 373. Find K Pairs with Smallest Sums
|
算法 Python
LeetCode 295. Find Median from Data Stream
中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
97 0
LeetCode 295. Find Median from Data Stream
|
索引
LeetCode 287. Find the Duplicate Number
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
84 0
LeetCode 287. Find the Duplicate Number
|
索引
LeetCode 162. Find Peak Element
给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。 数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
97 0
LeetCode 162. Find Peak Element
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game