剑指offer系列37----数据流中的中位数

 1 package com.exe8.offer;
 2 
 3 import java.util.ArrayList;
 4 
 5 /**
 6  * 【题目】如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，
 7  *            那么中位数就是所有数值排序之后位于中间的数值。
 8  *       如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 9  *         Arraylist:  底层的数据结构使用的是数组结构，
10  　　　　　　特点： 查询速度很快，但是增删稍慢。线程不同步
11              LinkedList： 底层使用的是链表数据结构。
12  　　　　　　特点： 增删速度很快，查询稍慢。
13  * @author WGS
14  *
15  */
16 public class GetMidMum {
17       ArrayList<Integer> list = new ArrayList<Integer>();
18       //插入排序法，按从小到大顺序
19       public void Insert(Integer num) {
20         int index=0;
21         int size=list.size();
22         while(index<size){
23             if(num<=list.get(index))
24                 break;//如果添加的值小于list index处的数,就放在此位置
25             index++;
26       }
27         list.add(index,num);
28       }
29     public Double GetMedian() {
30         int size=list.size();
31         if((size &1 )==0) //偶数
32             return (double)( (list.get(size/2-1))+(list.get(size/2))/2.0);;
33         return (double)list.get((size-1)/2);
34        
35     }
36     public static void main(String[] args) {
37         GetMidMum g=new GetMidMum();
38         g.Insert(2);
39         g.Insert(3);
40         g.Insert(1);
41         g.Insert(5);
42         System.out.println(g.GetMedian());
43 
44     }
45 
46 }