一道简约而不简单的算法题--数据流的中位数

题目来源于 LeetCode 上第 295 号问题:数据流的中位数。难度级别为 Hard,目前通过率为 33.5% 。

题目描述

中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构:

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

输入:

输入

输入

输出:

输出

输出

题目解析

这道题给我们一个数据流,让我们找出中位数。对于数据流这种动态(流动)的数据,如果使用数组存储,那么每次新进来一个数据都进行排序的话,效率很低。

处理动态数据来说一般使用的数据结构是栈、队列、二叉树、堆。

本题中,我们使用 这种数据结构。

top Created with Sketch.