一道求中位数的面试题

[yujianwjj]

一个数组，不停的往里面添加数字，要求 O(1) 复杂度求数组中位数。

[hcocoa]

空间换时间

[imn1]

你这“中位数”是数学的中位数定义么——(最大值+最小值)/2 ？
如果是的话，只需要比较初始最大最小值和添加值而已啊

[chibupang]

用最大堆最小堆分别存一半的数据，再往后，答案就很明显了。

[liyunlong41]

添加的时候实时计算中位数即可，比如一开始有一个数，中位数就是这个数下标，然后根据中位数和添加的数的大小比较，确定中位数应该往左移还是右移，实时维护中位数位置。

[yujianwjj]

@chibupang 懂了

[noqwerty]

@imn1 中位数不是这么定义的啊大兄弟

[fishCatcher]

@chibupang 可是每次插入新数时，调整要 O(logn)啊？

[imn1]

@noqwerty #6
那就是统计学的中位数了
不过也是，面试题也不会这么简单~

[fookwood]

Leetcode 题目链接 https://leetcode-cn.com/problems/find-median-from-data-stream/
题解 https://leetcode-cn.com/problems/find-median-from-data-stream/solution/shu-ju-liu-de-zhong-wei-shu-by-leetcode/

[inhzus]

@fishCatcher #7 两个函数，插入 O(logn)，计算中位数 O(1)。楼主说的 O(1) 应该指的是后者的时间复杂度

[pipapa]

@imn1 统计学也不是这样定义的吧

[yclissetj]

原题没给出时间复杂度的要求，题解里最好也是 O(nlogn) 呀 。。
https://leetcode.com/problems/find-median-from-data-stream/

[yclissetj]

@yclissetj sorry，O(logn) ...