剑指Offer系列之「数据流中的中位数」

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

方法一：暴力法

暴力法无非就是每次插入一个元素，不做操作，但是取的时候，每次都要排序，然后取中位数。 这里不再赘述。

时间复杂度：Insert()为O(1), GetMedian()为O(nlogn) 空间复杂度：O(n)

方法二：插入排序 方法一中GetMEdian()操作，是每次都对整个数组调用排序操作。 但是其实每次都是在一个有序数组中插入一个数据。因此可以用插入排序。 所以：

Insert()操作可改为插入排序 GetMedian()操作可直接从有序数组中获取中位数

时间复杂度：Insert()为O(n)，即二分查找的O(logn)和挪动数据的O(n)，GetMedian()为O(1) 空间复杂度：O(n)

方法三：堆思想

维护两个堆，一个大顶堆，一个小顶堆；通过一定的规则时刻保持大顶堆中的元素个数与小顶堆中的元素个数之间的差值不大于1；这里默认两堆个数之和为奇数时，就是大顶堆的顶元素，如果是偶数个，则为两堆顶元素和的平均值。 import java.util.*; public class Solution { private int count; private PriorityQueue<Integer> low = new PriorityQueue<>(); private PriorityQueue<Integer> high = new PriorityQueue<>( new Comparator<Integer>(){ public int compare(Integer o1, Integer o2){ return o2.compareTo(o1); } } ); public void Insert(Integer num) { count++; if((count & 1) == 1){ if(!low.isEmpty() && num > low.peek()){ low.offer(num); num = low.poll(); } high.offer(num); }else{ if(!high.isEmpty() && num < high.peek()){ high.offer(num); num = high.poll(); } low.offer(num); } } public Double GetMedian() { double res = 0; if((count & 1) == 1){ res = high.peek(); }else{ res = (high.peek() + low.peek()) / 2.0; } return res; } }

时间复杂度：Insert()为O(logn)，GetMedian()为O(1) 空间复杂度：O(n)