数字是不断进入数组的，在每次添加一个新的数进入数组的同时返回当前新数组的中位数。

说明

中位数的定义：

• 这里的中位数不等同于数学定义里的中位数。
• 中位数是排序后数组的中间值，如果有数组中有 n 个数，则中位数为 A[(n−1)/2]。
• 比如：数组 A=[1,2,3]的中位数是 2，数组 A=[1,19]的中位数是 1 。

点此在线做题

样例 1

输入: [1,2,3,4,5] 输出: [1,1,2,2,3] 样例说明： [1] 和 [1,2] 的中位数是 1. [1,2,3] 和 [1,2,3,4] 的中位数是 2. [1,2,3,4,5] 的中位数是 3. 

样例 2

输入: [4,5,1,3,2,6,0] 输出: [4,4,4,3,3,3,3] 样例说明： [4], [4,5] 和 [4,5,1] 的中位数是 4. [4,5,1,3], [4,5,1,3,2], [4,5,1,3,2,6] 和 [4,5,1,3,2,6,0] 的中位数是 3. 

题解

用 maxheap 保存左半部分的数，用 minheap 保存右半部分的数。 把所有的数一左一右的加入到每个部分。左边部分最大的数就一直都是 median 。 这个过程中，可能会出现左边部分并不完全都 <= 右边部分的情况。这种情况发生的时候，交换左边最大和右边最小的数即可。

public class Solution {     /**      * @param nums: A list of integers.      * @return: the median of numbers      */     private PriorityQueue<Integer> maxHeap, minHeap;     private int numOfElements = 0;      public int[] medianII(int[] nums) {         // write your code here         Comparator<Integer> revCmp = new Comparator<Integer>() {             @Override             public int compare(Integer left, Integer right) {                 return right.compareTo(left);             }         };         int cnt = nums.length;         maxHeap = new PriorityQueue<Integer>(cnt, revCmp);         minHeap = new PriorityQueue<Integer>(cnt);         int[] ans = new int[cnt];         for (int i = 0; i < cnt; ++i) {             addNumber(nums[i]);             ans[i] = getMedian();         }         return ans;     }     void addNumber(int value) {         maxHeap.add(value);         if (numOfElements%2 == 0) {             if (minHeap.isEmpty()) {                 numOfElements++;                 return;             }             else if (maxHeap.peek() > minHeap.peek()) {                 Integer maxHeapRoot = maxHeap.poll();                 Integer minHeapRoot = minHeap.poll();                 maxHeap.add(minHeapRoot);                 minHeap.add(maxHeapRoot);             }         }         else {             minHeap.add(maxHeap.poll());         }         numOfElements++;     }     int getMedian() {         return maxHeap.peek();     } }