【Leetcode】295. 数据流的中位数

忘是亡心i 2022-09-09 04:38 130阅读 0赞

### 295. 数据流的中位数 ###

*  题目描述
 *  解题思路
 *   *  方法1：优先队列
     *  方法2：有序集合+双指针

# 题目描述 #

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。  
例如，  
\[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;
        }
    }

**复杂度分析**  
时间复杂度：

*   addNum : O ( log ⁡ n ) \\textit\{addNum\}: O(\\log n) addNum:O(logn)，其中 n 为累计添加的数的数量。
 *   findMedian : O ( 1 ) \\textit\{findMedian\}: O(1) 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 SortedList
    
    
    class MedianFinder:
        def __init__(self):
            self.nums = SortedList()
            self.left = self.right = None
            self.left_value = self.right_value = None
    
        def addNum(self, num: int) -> None:
            nums_ = self.nums
            n = len(nums_)
            nums_.add(num)
            if n == 0:
                self.left = self.right = 0
            else:
                # 模拟双指针，当 num 小于 self.left 或 self.right 指向的元素时，num 的加入会导致对应指针向右移动一个位置
                if num < self.left_value:
                    self.left += 1
                if num < self.right_value:
                    self.right += 1
    
                if n & 1:
                    if num < self.left_value:
                        self.left -= 1
                    else:
                        self.right += 1
                else:
                    if self.left_value < num < self.right_value:
                        self.left += 1
                        self.right -= 1
                    elif num >= self.right_value:
                        self.left += 1
                    else:
                        self.right -= 1
                        self.left = self.right
            self.left_value = nums_[self.left]
            self.right_value = nums_[self.right]
    
        def findMedian(self) -> float:
            return (self.left_value + self.right_value) / 2
    
    
    if __name__ == "__main__":
        medianfinder = MedianFinder()
        medianfinder.addNum(3)
        medianfinder.addNum(2)
        medianfinder.addNum(5)
        print(medianfinder.findMedian())
        medianfinder.addNum(4)
        print(medianfinder.findMedian())

**复杂度分析**  
时间复杂度：

*   addNum : O ( log ⁡ n ) \\textit\{addNum\}: O(\\log n) addNum:O(logn)，其中 n 为累计添加的数的数量。
 *   findMedian : O ( 1 ) \\textit\{findMedian\}: O(1) findMedian:O(1)。

空间复杂度：

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

--------------------

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