这是一个创建于 2133 天前的主题，其中的信息可能已经有所发展或是发生改变。
一个数组，不停的往里面添加数字，要求 O(1) 复杂度求数组中位数。
 |
1
hcocoa 2020 年 3 月 12 日
空间换时间
|
 |
2
imn1 2020 年 3 月 12 日
你这“中位数”是数学的中位数定义么——(最大值+最小值)/2 ？
如果是的话，只需要比较初始最大最小值和添加值而已啊 |
 |
3
chibupang 2020 年 3 月 12 日 via iPhone
用最大堆最小堆分别存一半的数据，再往后，答案就很明显了。
|
 |
4
liyunlong41 2020 年 3 月 12 日 via iPhone  1
添加的时候实时计算中位数即可，比如一开始有一个数，中位数就是这个数下标，然后根据中位数和添加的数的大小比较，确定中位数应该往左移还是右移，实时维护中位数位置。
|
 |
7
fishCatcher 2020 年 3 月 12 日 via iPhone
@chibupang 可是每次插入新数时，调整要 O(logn)啊？
|
 |
9
fookwood 2020 年 3 月 12 日
|
 |
10
inhzus 2020 年 3 月 12 日
@fishCatcher #7 两个函数，插入 O(logn)，计算中位数 O(1)。楼主说的 O(1) 应该指的是后者的时间复杂度
|
 |
12
yclissetj 2020 年 3 月 12 日 via iPad
原题没给出时间复杂度的要求，题解里最好也是 O(nlogn) 呀 。。
https://leetcode.com/problems/find-median-from-data-stream/ |
Select Language