数据流中的中位数

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

解题思路：使用最大堆和最小堆,如果插入个数是奇数,则是中间的数,如果是偶数,则是中间两数之和的一半,比如1，2，3，4，5，6，那么中位数就是中间两位之和的一半，现在问题就转换为怎么定位这两个数，所以可以使用最大堆和最小堆，根据堆的性质，最大堆的堆顶元素最大，最小堆的堆顶元素最小，最大堆用于保存前半部分的数（1，2，3）,最小堆用于保存后半部分的数（4，5，6），当插入的个数是奇数时,返回最大堆的堆顶即是中位数,如果是偶数,则是最大堆的堆顶和最小堆的堆顶之和的一半，;此时最大堆的堆顶元素为3，最小堆的堆顶为4，所以中位数为两者之和的一半（3+4）/ 2.0 = 3.5。

public class Solution {    private int cnt = 0;    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) {        ++cnt;         if((cnt & 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() {        if((cnt & 1) == 1){   //插入个数为奇数            return high.peek() * 1.0;        }else{      //插入个数为偶数            return (high.peek() + low.peek()) / 2.0;

}}

}

更多相关文章

随机推荐