题

题目描述

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

ps：这几首随机播放的歌都太好听了！涵盖了中文，日文，不知道什么语言，经查证，应该是法语：La gloire à mes genoux；

解

基本思路是这样：维护两个堆，一个是小顶堆，其中存数据流中较大的一半数据，堆顶元素为较大元素中最小的一个；

一个是大顶堆，存数据流中较小的一半数据，堆顶元素是较小元素中最大的一个。

保证：

1）小顶堆中元素都大于大顶堆中元素；

2）小顶堆中元素个数大于等于大顶堆中元素，最大不超过大顶堆元素个数+1；

更新过程，增加元素num：

如果当前元素个数是偶数个，增加一个元素到小顶堆中（因为小顶堆中元素个数总是多的一方）；

增加的这个元素要满足：是{num，大顶堆中元素}中最大的一个。所以采取的方法是：先将元素加入大顶堆，然后pop堆顶元素（即最大元素），加入小顶堆。

如果当前元素个数是奇数个，相同的道理。

特别的：

1）PriorityQueue，默认是构造的小顶堆；

2）关于自定义比较器Comparator

import java.util.PriorityQueue;import java.util.Comparator;public class Solution {
       // 保证小顶堆中数据都大于大顶堆中数据；且小顶堆数据个数等于或等于大顶堆中数据个数+1；    int count = 0;    PriorityQueue
   
     min = new PriorityQueue<>(); //小顶堆，    // 大顶堆，元素按从大到小排    PriorityQueue
    
      max = new PriorityQueue<>(new Comparator
     
      (){
           @Override        public int compare(Integer a, Integer b){
               return b - a;        }    });        public void Insert(Integer num) {
           if((count & 1) == 1){
               // 即是奇数，大顶堆中增加一个元素            // 增加的元素为：num和小顶堆中元素的最小值            min.offer(num);            int cur = min.poll(); // 取堆顶元素，即最小者            max.offer(cur);        }else{
               // 偶数个元素，向小顶堆中增加一个元素（小顶堆中元素大于等于大顶堆中元素个数）            // 增加的元素为：num和大顶堆中最大的元素            max.offer(num);            int cur = max.poll();            min.offer(cur);        }        count++;    }    public Double GetMedian() {
           if((count & 1) == 1){
               // 即奇数个元素            return min.peek() * 1.0;        }else{
               return (min.peek() + max.peek()) / 2.0;        }    }}

转载地址：http://mgwji.baihongyu.com/

你可能感兴趣的文章