题解 | 数据流中的中位数- 优化暴力算法 插入排序

import java.util.*;

/**
    插入排序的方法
 */
public class Solution {

    int size = 0;
    List<Integer> list = new
    ArrayList<>(); // 相较简单粗暴的方法 保存了上一次的插入时的排序 这样本次就不用耗费时间去排序

    public void Insert(Integer num) {
        int i = 0;
        while (i < size) {
            if (list.get(i) > num) {
                break;
            }
            i++;
        }
        if (i==size) {
            list.add(num);
        } else {
            list.add(i, num);
        }
        size++;
    }

    public Double GetMedian() {
        int n = size / 2;
        int m = size % 2;
        if (m == 0) {
            int sum = list.get(n - 1) + list.get(n);
            return sum * 1.0 / 2;
        } else {
            return list.get(n) * 1.0;
        }
    }


}