Google 面试题 | Data Stream Median

(点击上方关注九章算法，获取最新IT求职干货！)

题目描述

持续给出数字，返回每次新增一个新的数时当前数组内的中位数。

注：中位数是指排好序的数组中位于中间位置的数。如果数组nums（已排好序）有n个数，那么其中位数是nums[(n - 1) / 2]。比如，nums = [1, 2, 3]，中位数是2；如果nums = [1, 19]，那么中位数是1。

Example：

持续给出的数字是：[4, 5, 1, 3, 2, 6, 0]，那么得到的中位数列表就是 [4, 4, 4, 3, 3, 3, 3]。

解题思路

1. 暴力解法：当添加一个新元素的时候，对已有数组进行排序，然后获取 nums[(n - 1) / 2]。这种解法的算法复杂度是O(n*nlogn)。

2. 改进：能不能不要每次都重新排序？可以。那我们维护一个已排序好的数组，每次新加一个元素的时候插入到这个数组里，然后获取nums[(n - 1) / 2]。查找插入的位置可以用二分法，复杂度是O(logn)，但是插入操作的复杂度是O(n)。所以整个算法的复杂度是O(n^2)。

3. 再改进：插入操作太消耗时间，能不能优化插入操作？可以。对于这种排好序的数组，想要在O(logn)时间内进行插入/删除，马上就想到Binary Search Tree。C++的STL里有现成的容器：set、map、multiset、multimap，都是用红黑树实现的。这样整个算法的复杂度就是O(nlogn)。

4. 再再改进：前面三个思路中，我们都是维护当前得到的所有n个元素，然后获取中间位置的那个。能不能不维护全部n个元素呢？可以。因为目标是第(n - 1) / 2 个元素，所以我们可以只维护前 k 大的元素（k = (n - 1) / 2），剩下的 (n - k) 个元素就放在备选区里。每次当新增一个元素的时候，从备选区所有元素和新增元素中选最大的那个元素加入到前 k 大里面。

a. 那么该使用哪个数据结构来维护前 k 大的元素呢？没错，就是小根堆。依次将 k 个元素插入堆里，堆顶元素便是第 k 大的元素。接下来对于新添的元素，将其与堆顶元素（第k大的数）进行比较，如果比第 k 大元素还大的话，那么插入前 k 大的这个堆里；如果比它小的话，放入备选区中，并且取备选区中最大的那个元素插入前 k 大。

b. 如何得到剩下的 (n - k) 中最大的元素呢？

1) 扫描剩下的 (n - k) 个元素，获取最大值。这样的复杂度是O(n)，导致整个算法复杂度是O(n^2)。

2) 用另一个堆（大根堆）！插入/删除的复杂度是O(logn)，获取最大值的复杂度是O(1)。

这样，使用两个堆（小根堆和大根堆），就能解决这个问题了，整个算法复杂度是O(nlogn)。

参考程序

登陆九章算法官网：www.jiuzhang.com获取更多面试题及答案。

http://www.jiuzhang.com/solutions/data-stream-median/