[编程题]数据流中的中位数

数据流中的中位数

http://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1

import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
        //小顶堆,从小到大排列
        private PriorityQueue<Integer> min=new PriorityQueue<Integer>();
        //大顶堆,从大到小的排列
        private PriorityQueue<Integer> max=new PriorityQueue<Integer>(15,new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return o2-o1;
            }
        });
        //如果当前的数据个数为0
        int count=0;
    public void Insert(Integer num) {
        if(count%2==0){
            max.offer(num);
            Integer curNum=max.poll();
            min.offer(curNum);
        }else{
            //如果为奇数
            min.offer(num);
            Integer curNum=min.poll();
            max.offer(curNum);
        }
        //插入一个数据后加1
        count++;
    }

    public Double GetMedian() {
        //如果输入流的数据个数为奇数
        if(count%2==0){
            return new Double(min.peek()+max.peek())/2;
        }else{
            return new Double(min.peek());
        }
    }


}
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务