LeetCode 题解工作台
数据流的中位数
中位数 是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。 例如 arr = [2,3,4] 的中位数是 3 。 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。 实现 MedianFinder 类: MedianFinder(…
5
题型
9
代码语言
3
相关题
当前训练重点
困难 · 双·指针·invariant
答案摘要
我们可以使用两个堆来维护所有的元素，一个小根堆 和一个大根堆 ，其中小根堆 存储较大的一半，大根堆 存储较小的一半。 调用 `addNum` 方法时，我们首先将元素加入到大根堆 ，然后将 的堆顶元素弹出并加入到小根堆 。如果此时 的大小与 的大小差值大于 ，我们就将 的堆顶元素弹出并加入到 。时间复杂度为 $O(\log n)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
-
MedianFinder()初始化MedianFinder对象。 -
void addNum(int num)将数据流中的整数num添加到数据结构中。 -
double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
示例 1：
输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0] 解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
提示:
-105 <= num <= 105- 在调用
findMedian之前，数据结构中至少有一个元素 - 最多
5 * 104次调用addNum和findMedian
解题思路
方法一：大小根堆（优先队列）
我们可以使用两个堆来维护所有的元素，一个小根堆 和一个大根堆 ，其中小根堆 存储较大的一半，大根堆 存储较小的一半。
调用 addNum 方法时，我们首先将元素加入到大根堆 ，然后将 的堆顶元素弹出并加入到小根堆 。如果此时 的大小与 的大小差值大于 ，我们就将 的堆顶元素弹出并加入到 。时间复杂度为 。
调用 findMedian 方法时，如果 的大小等于 的大小，说明元素的总数为偶数，我们就可以返回 的堆顶元素与 的堆顶元素的平均值；否则，我们返回 的堆顶元素。时间复杂度为 。
空间复杂度为 。其中 为元素的个数。
class MedianFinder:
def __init__(self):
self.minq = []
self.maxq = []
def addNum(self, num: int) -> None:
heappush(self.minq, -heappushpop(self.maxq, -num))
if len(self.minq) - len(self.maxq) > 1:
heappush(self.maxq, -heappop(self.minq))
def findMedian(self) -> float:
if len(self.minq) == len(self.maxq):
return (self.minq[0] - self.maxq[0]) / 2
return self.minq[0]
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates understanding of heap-based solutions for median tracking.
- question_mark
Candidate should be able to explain the trade-off of using two heaps versus other approaches.
- question_mark
Watch for the candidate's ability to efficiently manage heap balancing and handle edge cases.
常见陷阱
外企场景- error
Failing to properly balance the heaps after adding a number can result in incorrect median calculations.
- error
Not handling edge cases where the number of elements is small (e.g., only one element).
- error
Overcomplicating the solution by using other data structures that don’t offer efficient median tracking.
进阶变体
外企场景- arrow_right_alt
Implementing median calculation with a different data structure like a balanced binary search tree.
- arrow_right_alt
Optimizing for space complexity by reducing the number of stored elements in memory.
- arrow_right_alt
Handling a continuous stream of data in real-time with additional constraints.