这是一个创建于 2234 天前的主题，其中的信息可能已经有所发展或是发生改变。
一个数组，不停的往里面添加数字，要求 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