题目描述

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5

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

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-median-from-data-stream

---

示例

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

进阶

1. 如果数据流中所有整数都在0到100范围内，你将如何优化你的算法？
2. 如果数据流中99%的整数都在0到100范围内，你将如何优化你的算法？

解题思路

方法1：优先队列

定义两个优先队列queueMax和queueMin，其中：

• queueMax：记录大于中位数的数
• queueMin：记录小于等于中位数的数。

1. 当累计添加的数的数量为奇数时，queueMin中的数的数量比queueMax多一个（中位数放在了queueMin队列中），此时中位数为queueMin的队头。
2. 当累计添加的数的数量为偶数，两个优先队列中的数的数量相同，此时中位数就是它们的队头的平均值。

当我们尝试添加一个数num到数据结构中，需要分情况讨论：

1. num<=max{queueMin}
   此时num小于等于中位数，需要将该数添加到queueMin中。新的中位数将小于等于原来的中位数，因此需要将queueMin中最大的数移动到queueMax中。
2. num>max{queueMin}
   此时num大于中位数，需要将该数添加到queueMax中。新的中位数将大于等于原来的中位数，因此我们可能需要将queueMax中最小的数移动到queueMin中。

注意，当累计添加的数的数量为0时，将num添加到queueMin中。
代码如下：

package com.seckill.secondkill.utils;import java.util.PriorityQueue;class MedianFinder {public static PriorityQueue<Integer> queMin;public static PriorityQueue<Integer> queMax;public MedianFinder() {queMin = new PriorityQueue<>((a, b) -> (b - a));queMax = new PriorityQueue<>((a, b) -> (a - b));}public void addNum(int num) {// 首先将元素加入到最小堆中if (queMin.isEmpty() || num <= queMin.peek()) {queMin.offer(num);if (queMax.size() + 1 < queMin.size()) {queMax.offer(queMin.poll());}} else {queMax.offer(num);if (queMax.size() > queMin.size()) {queMin.offer(queMax.poll());}}}public double findMedian() {if (queMin.size() > queMax.size()) {return queMin.peek();}return (queMin.peek() + queMax.peek()) / 2.0;}
}

复杂度分析
时间复杂度：

• $\text{addNum}:O(\log n)$，其中 n 为累计添加的数的数量。
• $\text{findMedian}:O(1)$。

空间复杂度：O(n)，主要为优先队列的开销。

方法2：有序集合+双指针

使用有序集合维护这些数，把有序集合看作自动排序的数组，使用双指针指向有序集合中的中位数元素即可。当累计添加的数的数量为奇数时，双指针指向同一个元素。当累计添加的数的数量为偶数时，双指针分别指向构成中位数的两个数。

当尝试添加一个数num到数据结构中，需要分情况讨论：

1. 初始化有序集合为空，直接让左右指针指向num所在的位置；
2. 有序集合中元素个数为奇数时，left和right同时指向中位数。如果num大于等于中位数，那么只要让left左移，否则让right右移即可；
3. 有序集合中元素个数为偶数时，left和right分别指向构成中位数的两个数。
   • 当num成为新的 唯一的中位数，那么让left右移，right左移，这样它们即可指向num所在的位置；
   • 当num大于等于 right，那么让left右移即可；
   • 当num小于right指向的值，那么我们让right左移，注意到如果num等于left指向的值，那么num将被插入到left的右侧，使得left和right间距增大，所以还需要额外让left指向移动后的right。

代码如下：

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName  :MedianFinder.py
# @Time      :2021/10/8 11:02
# @Author    :PangXZ
from sortedcontainers import SortedListclass MedianFinder:def __init__(self):self.nums = SortedList()self.left = self.right = Noneself.left_value = self.right_value = Nonedef addNum(self, num: int) -> None:nums_ = self.numsn = len(nums_)nums_.add(num)if n == 0:self.left = self.right = 0else:# 模拟双指针，当 num 小于 self.left 或 self.right 指向的元素时，num 的加入会导致对应指针向右移动一个位置if num < self.left_value:self.left += 1if num < self.right_value:self.right += 1if n & 1:if num < self.left_value:self.left -= 1else:self.right += 1else:if self.left_value < num < self.right_value:self.left += 1self.right -= 1elif num >= self.right_value:self.left += 1else:self.right -= 1self.left = self.rightself.left_value = nums_[self.left]self.right_value = nums_[self.right]def findMedian(self) -> float:return (self.left_value + self.right_value) / 2if __name__ == "__main__":medianfinder = MedianFinder()medianfinder.addNum(3)medianfinder.addNum(2)medianfinder.addNum(5)print(medianfinder.findMedian())medianfinder.addNum(4)print(medianfinder.findMedian())

复杂度分析
时间复杂度：

• $\text{addNum}:O(\log n)$，其中 n 为累计添加的数的数量。
• $\text{findMedian}:O(1)$。

空间复杂度：

• O(n)，主要为有序集合的开销。

---

进阶问题1：
如果数据流中所有整数都在0到100范围内，那么可以根据计数排序统计每一类数的数量，并使用双指针维护中位数。
进阶问题2：
如果数据流中99%的整数都在0到100范围内，那么依旧可以利用计数排序统计每一类的数量，并使用双指针维护中位数。对于超出范围的数，可以单独进行处理，建立两个数组，分别记录小于0的部分的数的数量和大于100的部分的数的数量即可。当小部分时间，中位数不落在区间[0,100]中时，在对应的数组中暴力检查即可。