题解 | 数据流中的中位数

import java.util.*;


public class Solution {

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

    public void Insert(Integer num) {
        // list中没有元素，直接插入
        if (list.isEmpty()) {
            list.add(num);
        } else {
            int i = 0;
            // 遍历找到插入点
            for (; i < list.size(); i ++) {
                if (num <= list.get(i)) break;
            }
            // 插入相应的位置
            list.add(i, num);
        }
    }

    public Double GetMedian() {
        int size = list.size();
        // 奇数个数字
        if (size % 2 == 1) {
            return (double) list.get(size / 2);
        } else {
            int midIndex1 = size / 2 - 1;
            int midIndex2 = size / 2;
            return (list.get(midIndex1) + list.get(midIndex2)) / 2.0;
        }
    }


}