数据流中的中位数

Find Median from Data Stream

问题：数据流中的中位数

考察：双指针、设计、排序

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/find-median-from-data-stream

Problem: Find Median from Data Stream

Patterns: Two Pointers, Design, Sorting

Recency: 2yr

Link: https://leetcode.com/problems/find-median-from-data-stream

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：维护一个大根堆保存较小的一半、一个小根堆保存较大的一半，并保持两个堆大小差不超过 1。中位数由堆顶或两个堆顶平均得到。

复杂度：插入 O(log n)，查询中位数 O(1)，空间 O(n)。