剑指offer系列之六十二：数据流中的中位数

题目描述

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

根据题目的意思，就是对数据流中的数据进行排序然后得到其中位数。要解决的关键问题是如何在读入数据的时候就对数据进行排序。实际上可以看成是插入排序算法的应用，可以维持一个List集合，保证每次读入数据集合中的数据都是排序的。基本思路是：从集合的第一个元素开始，依次比较与新读入的元素的大小关系，从而把新读入的数据插入到合适的位置。可以看出，这实际上就是插入排序的思想了。下面是具体实现的代码（已被牛客AC）：

import java.util.ArrayList;
public class Solution {

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

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

    public Double GetMedian() {
        int size = list.size();
        if ((size & 1) == 0)
            return (double) ((list.get(size / 2) + list.get(size / 2 - 1)) / 2.0);
        return (double)list.get(size / 2) * 1.0;
    }

}