【解题报告】【lintcode81】Data Stream Median

题意

给出一组数字，逐一输入，每输入一个数字，就输出已经输入数字排序后的中位数，即中间那个数字

解答

直接暴力很简单，但是时间复杂度很高，不符合性能要求。 时间复杂度要求是nlogn，可以想到的是快速排序和堆排序两种排序，再结合题目，我们选择堆 维护两个堆，一个堆比中位数小，一个比中位数大，我们称之为大堆，小堆 大堆是一个比中位数大的小根堆，堆顶是刚刚比中位数大的数 小堆是一个比中位数小的大根堆，堆顶是刚刚比中位数小的数 每次获得一个数的时候，先与目前的中位数比较，大就加入大堆，小就加入小堆，如果加入完毕之后两个堆的大小不一致了，就应该重新查找中位数了 1.如果大根堆比小根堆大，先把中位数放入小堆，再从大堆拿出堆顶 2.如果小堆比大堆大，同上 由于对堆的维护时间复杂度是logn满足了我们的需求 这样，我们就能每次logn的复杂度拿到中位数了

代码

public class Solution {
    /**
     * @param nums: A list of integers.
     * @return: the median of numbers
     */
  public int[] medianII(int[] nums) {
        // write your code here
         Comparator<Integer> cmp = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        };
        PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>(20,cmp);
        PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>(20,cmp);
        
        int median;
        int[] medians;
        if (nums == null ||nums.length == 0)
            return new int[]{};
        medians = new int[nums.length];
        median = nums[0];
        medians[0] = median;
        for(int i = 1;i < nums.length;i++){
            if (nums[i] < median){
                maxQueue.add(nums[i]);
            }else{
                minQueue.add(-1*nums[i]);
            }
            if (maxQueue.size() > minQueue.size()){
                 minQueue.add(-1*median);
                 median = maxQueue.poll();
            }else if (maxQueue.size() +1<minQueue.size()){
                maxQueue.add(median);
                median = -1*minQueue.poll();
            }
            medians[i] = median;
        }
        return medians;
    }
}