题解 | #数据流中的中位数#

import java.util.*;


public class Solution {

    //插入排序：将未插入数依次插入有序中，每次插入比较大小找到插入位置
   //由于数组是在不断增长的不能全部插入后进行排序，
    //所以用到插入排序边插入数据便排序

    private static ArrayList<Integer> ret = new ArrayList<>();
    public static void Insert(Integer num) {
        //当列表为空时直接插入
        if (ret.isEmpty())
            ret.add(num);
        else {
            //找到插入位置，
            int i=0;
            for (;i<ret.size();i++){
                if (num<= ret.get(i))
                    break;
            }

            ret.add(i,num);//插入，原位置的数会平移

           
        }
    }

    public static Double GetMedian() {
        int n = ret.size();
        if (n%2==1){
            return (double) ret.get(n / 2);
        }else {
            double a = ret.get(n/2);
            double b = ret.get(n/2 -1);
            return (a+b)/2;
        }
    }

}