480. Sliding Window Median (Hard)

https://leetcode.com/problems/sliding-window-median/

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Median
---------------               -----
[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

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note:
You may assume k is always valid, ie: k is always smaller than input array's size for non-empty array.

Hints

Solutions

class Solution {
    TreeSet<Integer> maxSet;
    TreeSet<Integer> minSet;
    int[] nums;

    public double[] medianSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        this.nums = nums;
        // 注意处理 nums[a]==nums[b] 的情况,不然会导致重复元素的 indices 无法被加入 
        Comparator<Integer> compare = (a, b) -> nums[a] == nums[b] ? a - b : Integer.compare(nums[a], nums[b]);
        maxSet = new TreeSet<>(compare.reversed());
        minSet = new TreeSet<>(compare);
        double[] rst = new double[nums.length - k + 1];
        for (int i = 0; i <= nums.length; i++) {
            if (i >= k) {
                rst[i - k] = getMedian();
                remove(i - k);
            }
            if (i < nums.length) {
                add(i);
            }
        }

        return rst;
    }

    // 使用 TreeSet 储存数组元素对应的下标来保证唯一性
    private void add(int index) {
        if (nums[index] > getMedian()) {
            minSet.add(index);
        } else {
            maxSet.add(index);
        }

        // Check the size of two Set is whether balanced or not
        // if not equal then maxSet will be larger by one
        if (maxSet.size() - minSet.size() > 1) {
            minSet.add(maxSet.pollFirst());
        } else if (maxSet.size() < minSet.size()) {
            maxSet.add(minSet.pollFirst());
        }
    }

    private double getMedian() {
        if (maxSet.isEmpty() && minSet.isEmpty()) {
            return 0;
        }

        // if the two sets' size is the same, get the average.
        // remember to convert int into double
        if (maxSet.size() == minSet.size()) {
            return ((double)nums[maxSet.first()] + (double)nums[minSet.first()]) / 2.0;
        // if the size is not the same, return the top value of maxSet
        // because the size of maxSet is larger than minSet by one.
        } else {
            return nums[maxSet.first()];
        }
    }

    private void remove(int index) {
        // remove时非常容易被忽略的点,参见分析 TreeSet 注意点3
        if (nums[index] <= getMedian()) {
            if (!maxSet.remove(index)) {
                minSet.remove(index);
            }
        } else {
            if (!minSet.remove(index)) {
                maxSet.remove(index);
            }
        }

        // Remove a value may cause the data structure lost balance,
        // so remember to rebalance the two heap here.
        if (maxSet.size() - minSet.size() > 1) {
            minSet.add(maxSet.pollFirst());
        } else if (maxSet.size() < minSet.size()) {
            maxSet.add(minSet.pollFirst());
        }
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-04-15 19:05:09

results matching ""

    No results matching ""