题解 | #随时找到数据流的中位数#

方法二 堆
思路

由于本题被划分为堆问题，所以可以考虑使用堆来解决问题，毕竟堆也是可以用来排序的；

由于中位数要求所给数据是已排序的，所以可以将排序数据分为两部分，分别为左边部分left以及右边部分right，两者之间需要满足一下关系：


由于中位数求值需要left的最大值，以及right的最小值，所以对left使用最大堆存储，使用最小堆存储right；

而当满足情况（1）时，中位数medium就是left.max与right.min的平均值，而对于情况（2）则中位数medium为left.max；


那么我们来说说插入的操作吧，首先我们需要确定插入时left与right的情况：
1.当满足情况（1）时，当插入一个数据num时，数据总数变为奇数，也就是说中位数会变为left.max，此时数据应该插入left中，但是由于left存储的是已排序的左边数据，而num现在无法确定其属于哪一边，所以无法直接将num插入left中，但是我们知道right是一个最小堆，所以我们可以先将num插入right中，此时right堆顶元素是right中的最小值，将其移入left中即可。

2.当满足情况（2）时，插入一个数据num，数据总数会变为偶数，也就是说中位数变为，此时数据应该插入right中，同样由于不知道num究竟属于哪一边，所以需要先将num插入left，取出最大值max插入right中。

插入数据的时间复杂度：O(logn)，每次添加数据时需要调整一次堆结构，时间复杂度为O(logn)；

查询中位数的时间复杂度：O(1)，中位数在插入数据时就已经计算好了，所以查询的时间为O(1)；

空间复杂度为O(n),存储数据。

import java.util.*;


public class Solution {

    /**
     * the medians
     * @param operations int整型二维数组 ops
     * @return double浮点型一维数组
     */
    public double[] flowmedian (int[][] operations) {

        // 存储中位数
        List<Double> list = new ArrayList<>();

        MedianHolder holder = new MedianHolder();

        for (int i = 0; i < operations.length; i++) {

            if (operations[i][0] == 1) {
                holder.add(operations[i][1]);
            }

            if (operations[i][0] == 2) {
                list.add(holder.getMedian());
            }
        }

        double[] medians = new double[list.size()];
        for (int j = 0; j < list.size(); j++) {
            medians[j] = list.get(j);
        }

        return medians;
    }

     class MedianHolder {
        double medianNum = -1;

        // 建立最小堆存放排序后的右边的数据，堆顶是右边数据的最小值
        PriorityQueue<Integer> rightMinHead = new PriorityQueue<>();

        // 建立最大堆，存放排序后左边的数据，堆顶是左边数据的最大值
        PriorityQueue<Integer> leftMaxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare (Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        public void add (int num) {

            // 如果新增一个数，元素的总数量为变为偶数
            if (leftMaxHeap.size() > rightMinHead.size()) {
                leftMaxHeap.offer(num);
                rightMinHead.offer(leftMaxHeap.poll());
                // 更新中位数
                medianNum = (leftMaxHeap.peek() + rightMinHead.peek()) / 2.0;
                return;
            } else {
                // 如果新增一个数，元素的总数量为变为奇数
                rightMinHead.offer(num);
                leftMaxHeap.offer(rightMinHead.poll());
                // 更新中位数
                medianNum = leftMaxHeap.peek();
                return;
            }
        }

        public double getMedian () {
            return this.medianNum;
        }
    }
}