算法学习之数据流中的中位数

题目描述

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

使用TreeMap的自然排序，key值会自动按从小到大排列，然后配合使用TreeMap的higherEntry获取相应的元素。思路简单清晰，本质使用了桶排序的方式。

import java.util.*; public class Solution { TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>(); public void Insert(Integer num) { // 利用TreeMap的自然排序让插入的元素的key从小到大排序，重复的元素value++统计个数 if(map.containsKey(num)){ int sum = map.get(num); map.replace(num,sum,sum+1); }else{ map.put(num,1); } } public Double GetMedian() { int size = map.size(); int mid = (size+1)/2; Map.Entry entry = map.firstEntry(); int i = (int)entry.getValue(); while(mid>i){ entry = map.higherEntry((int)entry.getKey()); // 获取最近的一个比当前key大的entry i+=(int)entry.getValue(); // 累加获取中心点 } if(size%2==0&& i == mid){ return (((int)entry.getKey()) * 1.0 + (int)map.higherEntry((int)entry.getKey()).getKey()* 1.0) / 2; } return (int)entry.getKey()*1.0; } }