题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
示例1
输入：[5,2,3,4,1,6,7,0,8]
返回值："5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
说明：数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...

题目分析

在存储数据的结构中，因为要能获得中位数，需要保持数据的有序性，同时方便直接访问中间数据，可以使用 arrayList 或 linkedList，前者查询速度快，后者插入速度快；
同时需要考虑一个问题，是在插入的时候就保持数据的有序性，还是在获取的时候才对数据排序。
这里可以根据具体的需求进行选择，若是插入操作很多，读取操作少的，可以选择在读取的时候才排序；若是插入操作少而读取操作多的，可以选择在插入时即保证有序。

解题思路

方法1：在获取时，对数据排序
插入的时候，可以对数据不进行排序，仍按照插入顺序插入；
但在获取中位数时，需要对数据排序，然后再进行取中间值；
排序的方法有：快速排序（nlogn），堆排序（nlogn），归并排序（nlogn）等，可以选择任意一种。

方法2：在插入时，对数据排序
如果想要在插入的时候就进行排序，可以在插入目标值的时候，使用二分法O(logn)进行插入位置的查找，同时考虑到使用的存储数据结构，若是arrayList则还需要O(n)的时间进行数据的移动，若是linkedList则只需要O(1)插入数据，不需要移动数据；
而对于获取数据来说，若使用arrayList，只需要O(1)的时间；使用linkedList需要O(n)的时间，所以可以以针对不同的需求和使用场景进行选择。
插入数据的过程如下：
图片说明

代码实现

方法1：在获取时，对数据排序

    // 使用ArrayList存储数据
    ArrayList<Integer> store = new ArrayList<Integer>();
    public void Insert(Integer num) {
        // 插入时不操作，直接插入
        store.add(num);
    }
    public Double GetMedian() {
        // 在获取中位数时
        int length = store.size();
        if(length == 0) return 0.0;
        if(length == 1) return store.get(0)/1.0;
        // 先对数据排序
        Collections.sort(store);
        // 再根据数据个数的奇偶性获取中位数
        int index = length/2;
        if(length%2 == 1){
            return store.get(index)/1.0;
        }else{
            return (store.get(index)+store.get(index-1))/2.0;
        }
    }

时间复杂度：插入方法只要直接在数据末尾添加，时间复杂度为O(1)；读取方法，每次都要重新对数据排序，使用的是快速排序方法，时间复杂度O(n*logn)；
空间复杂度：O(n)，需要使用额外的空间来存储数据，空间使用n；

方法2：在插入时，对数据排序

    ArrayList<Integer> res = new ArrayList<>();
    public void Insert(Integer num) {
        // 定义加入的下标位置
        int index = -1;
        if(!res.isEmpty()){
            // 不为空时，初始化为数组末尾
            index = res.size()-1;
        }
        // 进行插入排序，找到目标数字正确的插入位置
        while(index>=0 && num<res.get(index)){
            index--;
        }
        // index位置上的是刚比num小的数，插到它的后面
        res.add(index+1, num);
    }

    public Double GetMedian() {
        // 获取链表的中间结点位置
        int mid = res.size()/2;
        Double median = 0.0;
        if(res.size()%2==0){
            // 若是偶数，则是中间两个数的平均值
            median = Double.valueOf((res.get(mid)+res.get(mid-1))/2.0);
        }else{
            // 若是奇数，则是中间的数
            median = Double.valueOf(res.get(mid));
        }
        return median;
    }

时间复杂度：插入方法需要对数据进行大小比较，得到目标数据的插入位置，最差需要遍历前面的所有数据，时间复杂度为O(n)；读取方法，只需要直接获取中间的数据，时间复杂度O(1)；
空间复杂度：O(n)，需要使用额外的空间来存储数据，空间使用n。