例题1.数据流的中位数

• 链接：LeetCode295.数据流的中位数

思路

• 需要维护一个数据结构，可以快速插入数据，快速调整数据，并且可以动态获取中位数
• 维护两个堆，左侧大顶堆，右侧小顶堆，且左堆所有数的数值都$\leq$右堆的所有数的数值，左侧可以$O(1)$获取到左侧序列的最大值，右侧可以$O(1)$获取右侧序列的最小值，我们只需要把两个堆的数据个数调整成一个相对平衡的状态即可$O(1)$获取序列的中位数
• 数据插入：如果待插入的数小于等于左堆的堆顶，则插入左堆，如果大于左堆堆顶，插入右堆
• 我们可以在总数为奇数的情况下，让右堆的个数比左堆的个数多1，中位数为右堆的堆顶；在总数为偶数的情况下，让右堆的个数和左堆的个数相等，中位数为左右堆的堆顶平均值，调整平衡的时间为$O(logn)$

Java代码

class MedianFinder {
    PriorityQueue<Integer> left = new PriorityQueue<>((o1,o2)->o2-o1);//左边大根堆
    PriorityQueue<Integer> right = new PriorityQueue<>();//右边小根堆
    /** initialize your data structure here. */
    public MedianFinder() {

    }

    public void addNum(int num) {
        if(left.size() > 0 && num <= left.peek()) {
            left.offer(num);
        }
        else {
            right.offer(num);
        }
        while(right.size() > left.size()+1) left.offer(right.poll());
        while(right.size() < left.size()) right.offer(left.poll());
    }

    public double findMedian() {
        if(right.size() > left.size()) return (double)right.peek();
        else return ((double)left.peek() + (double)right.peek()) / 2;
    }
}

例题2.滑动窗口中位数

• 链接：LeetCode480.滑动窗口中位数

思路

• 维护一个对顶堆，且两堆大小之和为窗口长度k，如果窗口长度为偶数，则取两堆的堆顶平均值，如果窗口长度为奇数，则取右堆的堆顶
• 窗口向右移动的时候，需要把新数插入合适的堆，并且把移出窗口的数从相应的堆中删除

Java代码

class Solution {
    PriorityQueue<Integer> left = new PriorityQueue<>((o1,o2) -> Integer.compare(o2,o1));
    PriorityQueue<Integer> right = new PriorityQueue<>();
    public double[] medianSlidingWindow(int[] nums, int k) {

        for(int i = 0; i < k; i++) right.add(nums[i]);
        for(int i = 0; i < k/2; i++) left.add(right.poll());

        List<Double> list = new ArrayList<>();
        list.add(getMedium(k));

        for(int i = k; i < nums.length; i++){
            int x = nums[i], y = nums[i-k];
            if(x >= right.peek()) right.add(x);
            else left.add(x);

            if(y >= right.peek()) right.remove(y);
            else left.remove(y);

            while(left.size() > right.size()) right.add(left.poll());
            while(right.size() > left.size() + 1) left.add(right.poll());

            list.add(getMedium(k));
        }
        int n = nums.length;
        double[] res = new double[list.size()];
        for(int i = 0; i < res.length; i++) res[i] = list.get(i);
        return res;
    }

    double getMedium(int x){
        if((x & 1) == 1) return (double)right.peek();
        else {
            double sum = (double)left.peek() + (double)right.peek();
            return  sum / 2.0;
        }
    }
}