一道求中位数的面试题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1720 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

中位数

求数组

面试

添加

13 条回复 • 2020-03-12 21:55:28 +08:00

hcocoa

2020-03-12 19:40:13 +08:00

空间换时间

imn1

2020-03-12 20:11:43 +08:00

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

chibupang

2020-03-12 20:15:00 +08:00 via iPhone

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

liyunlong41

2020-03-12 20:28:45 +08:00 via iPhone

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

yujianwjj

2020-03-12 20:35:13 +08:00

@chibupang 懂了

noqwerty

2020-03-12 20:43:34 +08:00 via Android

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

fishCatcher

2020-03-12 20:52:27 +08:00 via iPhone

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

imn1

2020-03-12 21:22:49 +08:00

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

fookwood

2020-03-12 21:28:32 +08:00

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

2020-03-12 21:43:56 +08:00

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

pipapa

2020-03-12 21:44:07 +08:00

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

yclissetj

2020-03-12 21:54:52 +08:00 via iPad

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

yclissetj

2020-03-12 21:55:28 +08:00 via iPad

@yclissetj sorry，O(logn) ...