题意：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

解题思路

解法1：
1.用list存储，每次add完成之后，调用sort排序
2.findMedian，根据list.size()的长度的奇偶性，返回相应的结果即可

解法2：
1.解法1中，每次add完成之后，都需要重新排序，耗时较多，所以在此处我们想到，每次插入时，借助插入排序+二分查找的思想，减少排序带来的时间消耗

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1
class MedianFinder {
  List<Integer> list;

  public MedianFinder() {
    list = new ArrayList<>();
  }

  public void addNum(int num) {
    list.add(num);
    Collections.sort(list);
  }

  public double findMedian() {
    return list.size() % 2 == 1
        ? list.get(list.size() / 2)
        : (list.get(list.size() / 2) + list.get(list.size() / 2 - 1)) / 2D;
  }
}


##解法2
import java.util.ArrayList;
import java.util.List;

class MedianFinder {
    List<Integer> list = null;
    public MedianFinder() {
        list = new ArrayList<Integer>();
    }

    public void addNum(int num) {
        int left = 0, right = list.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (list.get(mid) < num) {
                left = mid + 1;
            } else if (list.get(mid) > num) {
                right = mid - 1;
            } else {
                left = mid;
                break;
            }
        }
        list.add(left, num);
    }

    public double findMedian() {
        if (list.size() % 2 == 0) {
            int k = list.size() / 2;
            return (list.get(k) + list.get(k - 1)) / 2d;
        } else {
            return list.get(list.size() / 2);
        }
    }
}