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

2023-11-19 14:45:28

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

进阶

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

解题思路

方法1：优先队列

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

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

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

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

num<=max{queueMin}
此时num小于等于中位数，需要将该数添加到queueMin中。新的中位数将小于等于原来的中位数，因此需要将queueMin中最大的数移动到queueMax中。
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到数据结构中，需要分情况讨论：

初始化有序集合为空，直接让左右指针指向num所在的位置；
有序集合中元素个数为奇数时，left和right同时指向中位数。如果num大于等于中位数，那么只要让left左移，否则让right右移即可；
有序集合中元素个数为偶数时，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]中时，在对应的数组中暴力检查即可。

码农公寓

295. 数据流的中位数

题目描述

解题思路

方法1：优先队列

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

相关文章