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