剑指 Offer 41. 数据流中的中位数

本问题对应的 leetcode 原文链接:剑指 Offer 41. 数据流中的中位数
具体对应打卡问题看这里:【排序算法运用】剑指 Offer 41. 数据流中的中位数

问题描述

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构:

  • void addNum(int num) – 从数据流中添加一个整数到数据结构中。
  • double findMedian() – 返回目前所有元素的中位数。

示例 1:

输入:
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出:[null,null,null,1.50000,null,2.00000]

示例 2:

输入:
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出:[null,null,2.00000,null,2.50000]

限制:

  • 最多会对 addNum、findMedian 进行 50000 次调用。

解题思路

视频讲解直达: 本题视频讲解

代码实现

class MedianFinder {
    Queue<Integer> min, max;
    /** initialize your data structure here. */
    public MedianFinder() {
        min = new PriorityQueue<>(); // 小根,保存较大的
        max = new PriorityQueue<>((x, y) -> (y - x));// 大根
    }

    public void addNum(int num) {
        // 如果是偶数
        if(min.size() == max.size()){
            min.add(num);
            max.add(min.poll());
        } else {
            max.add(num);
            min.add(max.poll());
        }
    }

    public double findMedian() {
        // 如果是偶数
        if(min.size() == max.size()){
            return (min.peek() + max.peek()) / 2.0;
        } else {
            return max.peek() * 1.0;
        }
    }
}

时间复杂度:1. 查找中位数 O(1), 2. 插入元素:O(logn)
空间复杂度:O(n)

发表回复

后才能评论