LeetCode——滑动窗口中位数

Q：中位数是有序序列最中间的那个数。如果序列的大小是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
[2,3,4]，中位数是 3
[2,3]，中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

示例：
给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。

窗口位置	中位数
[1 3 -1] -3 5 3 6 7	1
1 [3 -1 -3] 5 3 6 7	-1
1 3 [-1 -3 5] 3 6 7	-1
1 3 -1 [-3 5 3] 6 7	3
1 3 -1 -3 [5 3 6] 7	5
1 3 -1 -3 5 [3 6 7]	6

因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。

A：解题思路和剑指offer系列——63.数据流中的中位数相同
运用一个大根堆和一个小跟堆处理。

    public double[] medianSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0 || k > nums.length) {
            return new double[]{};
        }
        double[] res = new double[nums.length - k + 1];
        if (k == 1) {
            for (int i = 0; i < nums.length; i++) {
                res[i] = nums[i];
            }
            return res;
        }
        ArrayList<Double> array = new ArrayList<>();
        PriorityQueue<Double> q1 = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Double> q2 = new PriorityQueue<>();
        int left = 0, right = 0;
        while (right < nums.length) {
            if (q1.isEmpty() || nums[right] <= q1.peek()) {
                q1.add((double) nums[right]);
            } else {
                q2.add((double) nums[right]);
            }
            right++;
            while (right - left > k) {
                if ((double) nums[left] <= q1.peek()) {
                    q1.remove((double) nums[left]);
                } else {
                    q2.remove((double) nums[left]);
                }
                left++;
            }
            if (k % 2 == 1) {
                while (q1.size() - q2.size() >= 2) {
                    q2.add(q1.poll());
                }
                while (q2.size() > q1.size()) {
                    q1.add(q2.poll());
                }
            } else {
                while (q1.size() > q2.size()) {
                    q2.add(q1.poll());
                }
                while (q2.size() > q1.size()) {
                    q1.add(q2.poll());
                }
            }
            if (right - left == k) {
                if (q1.size() > q2.size()) {
                    array.add(q1.peek());
                } else {
                    double temp = (q1.peek() + q2.peek()) / 2;
                    array.add(temp);
                }
            }
        }
        for (int i = 0; i < array.size(); i++) {
            res[i] = array.get(i);
        }
        return res;
    }

还是固定滑动窗口，先右后左，再处理窗口。