面试知识库

295. 数据流的中位数#

今天我们来聊一个非常有趣的题目 - 数据流中的中位数。这个问题看似简单，实则暗藏玄机，需要我们巧妙运用堆这个数据结构来解决。别担心！我会用最直观的方式，带你理解这个精妙的解决方案。

📚 生活中的中位数#

想象你是一个体育老师，正在记录学生们的跑步成绩。每当有新的同学完成跑步，你都需要立即知道到目前为止所有成绩的中位数。这就是我们今天要解决的核心问题！

问题描述#

题目目标#

中位数是有序整数列表中的中间值。如果列表长度为偶数，中位数是中间两个数的平均值。请设计一个支持以下操作的数据结构：addNum(int num) 用于向数据流中添加整数，findMedian() 用于返回当前所有元素的中位数。

示例 1#

输入：

["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
text

输出： [null,null,null,1.5,null,2.0] 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 问题是什么#

用大白话说：我们要设计一个数据结构，支持两个操作：

  1. 添加一个新的数字到我们的数据集中
  2. 随时可以获取当前所有数字的中位数

比如说：

// 假设数据流是：[4,5,8,2,3]
addNum(4)    // 插入 4 后，当前有序序列是 [4]，中位数为 4
addNum(5)    // 插入 5 后，当前有序序列是 [4,5]，中位数为 (4+5)/2 = 4.5
addNum(8)    // 插入 8 后，当前有序序列是 [4,5,8]，中位数为 5
addNum(2)    // 插入 2 后，当前有序序列是 [2,4,5,8]，中位数为 (4+5)/2 = 4.5
addNum(3)    // 插入 3 后，当前有序序列是 [2,3,4,5,8]，中位数为 4
java

🤔 为什么这个问题有趣？#

这个问题的挑战在于：

  1. 数据是流式输入的，我们不能预先知道所有数字
  2. 每次添加新数字后都要能快速得到中位数
  3. 数据规模可能很大，我们需要高效的解决方案

🚀 优雅的解决方案#

我们可以用两个堆来解决这个问题：

  • 一个大顶堆存储较小的一半数字
  • 一个小顶堆存储较大的一半数字

📝 代码是怎么工作的？#

让我们用一个具体的例子来看看这个结构是如何工作的：

假设数据流是：[4,5,8,2,3]

  1. 添加4：

    • smallerHalf: [4]
    • largerHalf: []
    • 中位数：4

  2. 添加5：

    • smallerHalf: [4]
    • largerHalf: [5]
    • 中位数：(4+5)/2 = 4.5

  3. 添加8：

    • smallerHalf: [4]
    • largerHalf: [5,8]
    • 平衡后：
      • smallerHalf: [4,5]
      • largerHalf: [8]
    • 中位数：5

依此类推…就像是在玩跷跷板，我们始终保持两边平衡，中位数自然就在中间！

🎯 要注意的关键点#

  1. 堆的选择

    • 为什么用大顶堆和小顶堆？
    • 这样可以方便地获取中间的数字

  2. 平衡的维护

    • 两个堆的大小差不超过1
    • 较小堆的最大值不超过较大堆的最小值

  3. 处理偶数和奇数的情况

    • 奇数个数时：中位数是较小堆的堆顶
    • 偶数个数时：中位数是两个堆顶的平均值

💡 生活中的类似场景#

这种设计思路在生活中很常见：

  1. 考试成绩统计

    • 实时计算班级的中等成绩
    • 新的成绩提交后快速更新

  2. 房价中位数

    • 房地产市场的价格中位数
    • 新房源上市后的即时统计

  3. 工资中位数

    • 公司薪资水平的中位数
    • 新员工入职后的即时更新

🎨 解决方案的可视化#

🌟 面试时怎么说？#

  1. 开场白

    • “我们可以用两个堆来维护数据流的中位数”
    • “一个堆存较小的一半，一个堆存较大的一半”

  2. 解释优势

    • 时间复杂度：添加数字O(logn)，查找中位数O(1)
    • 空间复杂度：O(n)存储所有数字

  3. 补充说明

    • 解决方案的可扩展性
    • 处理大数据流的能力

🎩 扩展思考#

这个解决方案的思路还可以用在其他场景：

  1. 滑动窗口中位数

    // 在固定大小的窗口内维护中位数
// 核心通常仍是双堆，但需要支持“删除窗口左端移出的元素”
class SlidingWindowMedian {
    // 常见实现：双堆 + 延迟删除（哈希表记录待删除计数）
}
    java

  2. 数据流的百分位数

    // 把“中位数（50%分位）”扩展为任意百分位（如 P90、P95）
class PercentileFinder {
    // 通过调整两侧数据比例，定位目标分位点对应的值
}
    java

这个双堆的设计非常优雅，它告诉我们：有时候把数据分成两半处理，反而能得到更简单的解决方案！

如果你对这个话题还有任何疑问，欢迎在评论区讨论！理解了这个问题，你会发现很多看似复杂的数据流问题都能用类似的思路来解决。