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

【题目】如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，

* 那么中位数就是所有数值排序之后位于中间的数值。

 package com.exe8.offer;

 import java.util.ArrayList;

 /**

  * 【题目】如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，

  *            那么中位数就是所有数值排序之后位于中间的数值。

  *       如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

  *         Arraylist:  底层的数据结构使用的是数组结构，

  　　　　　　特点： 查询速度很快，但是增删稍慢。线程不同步

              LinkedList： 底层使用的是链表数据结构。

  　　　　　　特点： 增删速度很快，查询稍慢。

  * @author WGS

  *

  */

 public class GetMidMum {

       ArrayList<Integer> list = new ArrayList<Integer>();

       //插入排序法，按从小到大顺序

       public void Insert(Integer num) {

         int index=0;

         int size=list.size();

         while(index<size){

             if(num<=list.get(index))

                 break;//如果添加的值小于list index处的数,就放在此位置

             index++;

       }

         list.add(index,num);

       }

     public Double GetMedian() {

         int size=list.size();

         if((size &1 )==0) //偶数

             return (double)( (list.get(size/2-1))+(list.get(size/2))/2.0);;

         return (double)list.get((size-1)/2);

     }

     public static void main(String[] args) {

         GetMidMum g=new GetMidMum();

         g.Insert(2);

         g.Insert(3);

         g.Insert(1);

         g.Insert(5);

         System.out.println(g.GetMedian());

     }

 }