一个数组,不停的往里面添加数字,要求 O(1) 复杂度求数组中位数。
1
hcocoa 2020-03-12 19:40:13 +08:00
空间换时间
|
2
imn1 2020-03-12 20:11:43 +08:00
你这“中位数”是数学的中位数定义么——(最大值+最小值)/2 ?
如果是的话,只需要比较初始最大最小值和添加值而已啊 |
3
chibupang 2020-03-12 20:15:00 +08:00 via iPhone
用最大堆最小堆分别存一半的数据,再往后,答案就很明显了。
|
4
liyunlong41 2020-03-12 20:28:45 +08:00 via iPhone 1
添加的时候实时计算中位数即可,比如一开始有一个数,中位数就是这个数下标,然后根据中位数和添加的数的大小比较,确定中位数应该往左移还是右移,实时维护中位数位置。
|
7
fishCatcher 2020-03-12 20:52:27 +08:00 via iPhone
@chibupang 可是每次插入新数时,调整要 O(logn)啊?
|
9
fookwood 2020-03-12 21:28:32 +08:00
|
10
inhzus 2020-03-12 21:43:56 +08:00
@fishCatcher #7 两个函数,插入 O(logn),计算中位数 O(1)。楼主说的 O(1) 应该指的是后者的时间复杂度
|
12
yclissetj 2020-03-12 21:54:52 +08:00 via iPad
原题没给出时间复杂度的要求,题解里最好也是 O(nlogn) 呀 。。
https://leetcode.com/problems/find-median-from-data-stream/ |