如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
示例 1：
输入： ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]] 输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入： ["MedianFinder","addNum","findMedian","addNum","findMedian"] [[],[2],[],[3],[]] 输出：[null,null,2.00000,null,2.50000]
限制：
addNum、findMedian 进行 50000 次调用。1 class MedianFinder { 2 List<Integer> arr; 3 /** initialize your data structure here. */ 4 public MedianFinder() { 5 this.arr=new ArrayList<>(); 6 } 7 8 public void addNum(int num) { 9 if(this.arr.size()==0){this.arr.add(num);} 10 else{ 11 int i=0; 12 //查找num插入的位置 13 for(;i<this.arr.size();i++){ 14 if(num<=this.arr.get(i)){ 15 this.arr.add(i,num); 16 break; 17 } 18 } 19 //没有遇到比num更大的数 20 if(i==this.arr.size()){ 21 this.arr.add(num); 22 } 23 } 24 } 25 26 public double findMedian() { 27 int t=this.arr.size(); 28 if(t%2==1){ 29 return this.arr.get(t/2); 30 }else{ 31 return (this.arr.get((t/2)-1)+this.arr.get((t/2)))/2.0; //下标从0开始所以要减1 32 } 33 34 } 35 } 36 37 /** 38 * Your MedianFinder object will be instantiated and called as such: 39 * MedianFinder obj = new MedianFinder(); 40 * obj.addNum(num); 41 * double param_2 = obj.findMedian(); 42 */
原文：https://www.cnblogs.com/SEU-ZCY/p/14627217.html