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.

Solutions

1.

class Solution {
    // Following solution can be simplified by using a single PriorityQueue to keep
    // the values in the window. It will become much easier to add and remove elements.
    // To get the median, move to the middle and return the value. If the window size is
    // odd, return the single middle value; if even, return the average of the middle two.

    Queue<Integer> smallerSet;
    Queue<Integer> largerSet;

    int[] nums;

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

        this.nums = nums;

        // We can use only one Tree to store the window values.
        // The reason of using two set instead one is that when we visit/remove
        // the elements of window, we don't have to go through the whole set.
        // The following structure facilitate us to manipulate the head only.

        // largerSet sorts elements by ascending order, not index
        largerSet = new PriorityQueue<>();

        // smallerSet sorts elements by descending order, not index

        // smallerSet = new PriorityQueue<>((o1, o2) -> o2 - o1);
        // Never use above expression, otherwise may cause overflow.
        // For instance, o2 = 2147483647 and o1 = -2147483648

        // Following two expressions are all workable

//            smallerSet = new PriorityQueue<>((o1, o2) -> -o1.compareTo(o2));

        smallerSet = new PriorityQueue<>(Comparator.reverseOrder());

        double[] ans = new double[nums.length - k + 1];

        for (int i = 0; i <= nums.length; i++) {
            if (i == 10) {
                System.out.println();
            }
            // Compute the median number until i is large than a single window size
            if (i >= k) {
                // Record the median number
                ans[i - k] = getMedian();

                // After right pointer proceeds one step, then remove the head index to
                // guarantee the window size is still equal to k
                remove(i - k);
            }

            // Move forward the window and add the newly visited index.
            if (i < nums.length) {
                add(i);
            }
        }

        return ans;
    }

    private double getMedian() {
        if (smallerSet.isEmpty() && largerSet.isEmpty()) {
            return 0;
        }

        // If the two sets is of the same size, get the average.
        if (smallerSet.size() == largerSet.size()) {
            // Remember to convert int into double.
            return smallerSet.peek() / 2.0 + largerSet.peek() / 2.0;
        }

        // If the size is not the same, return the top value of smallerSet
        // since the size of smallerSet is larger than largerSet by one.
        return smallerSet.peek();
    }

    private void add(int index) {
        // the parameter is index, not value

        // Values is largerSet is always larger than smallerSet since median is
        // from largerSet and smallerSet and only values greater than median
        // can be added to largerSet. So get the median and decide which set to insert.

        double median = getMedian();

        // Initially, the largerSet and smallerSet is empty hence the getMedian() returns 0
        if (nums[index] > median) {
            largerSet.add(nums[index]);
        }

        if (nums[index] <= median) {
            smallerSet.add(nums[index]);
        }

        // Check the size of two Set is whether balanced or not
        // if not equal then smallerSet will be larger by one

        balance();

    }

    private void remove(int index) {
        if (!smallerSet.remove(nums[index])) {
            largerSet.remove(nums[index]);
        }

        // Below commented out code is another approach to achieve above logic
        // which is more optimized than above
/*
        double median = getMedian();
        if (nums[index] <= median && !smallerSet.remove(index)) {
            largerSet.remove(index);
        }

        if (nums[index] > median && !largerSet.remove(index)) {
            smallerSet.remove(index);
        }
        */

        // Remove a value may cause the data structure unbalanced.
        // So remember to rebalance the two set here.

        balance();
    }

    private void balance() {
        // Guarantee 0 <= (smallerSet.size() - largerSet.size()) <= 1

        // Technically, size of smallerSet is not more larger than largerSet's by 1.
        // Because every time the unbalanced situation happens, following statements
        // will be executed to maintain the balance

        if (smallerSet.size() - largerSet.size() > 1) {
            largerSet.offer(smallerSet.poll());
        }

        // Similar with above logic

        if (smallerSet.size() < largerSet.size()) {
            smallerSet.offer(largerSet.poll());
        }
    }
}

2.

class Solution {
    // Following solution can be simplified by using a single PriorityQueue to keep
    // the values in the window. It will become much easier to add and remove elements.
    // To get the median, move to the middle and return the value. If the window size is
    // odd, return the single middle value; if even, return the average of the middle two.

    TreeSet<Integer> smallerSet;
    TreeSet<Integer> largerSet;
    int[] nums;

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

        this.nums = nums;

        // For same values, sort by it's index,
        // FYI, PriorityQueue is able to deal with the duplicate issue
        Comparator<Integer> compare = (a, b) -> nums[a] == nums[b] ? a - b : Integer.compare(nums[a], nums[b]);

        // We can use only one Tree to store the window values.
        // The reason of using two set instead one is that when we visit/remove
        // the elements of window, we don't have to go through the whole set.
        // The following structure facilitate us to manipulate the head only.

        // largerSet sorts elements by ascending order
        largerSet = new TreeSet<>(compare);

        // smallerSet sorts elements by descending order
        smallerSet = new TreeSet<>(compare.reversed());

        double[] ans = new double[nums.length - k + 1];

        for (int i = 0; i <= nums.length; i++) {
            // Compute the median number until i is large than a single window size
            if (i >= k) {
                // Record the median number
                ans[i - k] = getMedian();

                // After right pointer proceeds one step, then remove the head index to
                // guarantee the window size is still equal to k
                remove(i - k);
            }

            // Move forward the window and add the newly visited index.
            if (i < nums.length) {
                add(i);
            }
        }

        return ans;
    }

    private double getMedian() {
        if (smallerSet.isEmpty() && largerSet.isEmpty()) {
            return 0;
        }

        // If the two sets is of the same size, get the average.
        if (smallerSet.size() == largerSet.size()) {
            // Remember to convert int into double.
            return ((double) nums[smallerSet.first()] + (double) nums[largerSet.first()]) / 2.0;
        }

        // If the size is not the same, return the top value of smallerSet
        // since the size of smallerSet is larger than largerSet by one.
        return nums[smallerSet.first()];
    }

    private void add(int index) {

        // Values is largerSet is always larger than smallerSet since median is
        // from largerSet and smallerSet and only values greater than median
        // can be added to largerSet. So get the median and decide which set to insert.

        double median = getMedian();

        // Initially, the largerSet and smallerSet is empty hence the getMedian() returns 0
        if (nums[index] > median) {
            largerSet.add(index);
        }

        if (nums[index] <= median) {
            smallerSet.add(index);
        }

        // Check the size of two Set is whether balanced or not
        // if not equal then smallerSet will be larger by one

        balance();

    }

    private void remove(int index) {
        if (!smallerSet.remove(index)) {
            largerSet.remove(index);
        }

        // Below commented out code is another approach to achieve above logic
        // which is more optimized than above
/*
        double median = getMedian();
        if (nums[index] <= median && !smallerSet.remove(index)) {
            largerSet.remove(index);
        }

        if (nums[index] > median && !largerSet.remove(index)) {
            smallerSet.remove(index);
        }
        */

        // Remove a value may cause the data structure unbalanced.
        // So remember to rebalance the two set here.

        balance();
    }

    private void balance() {
        // Guarantee 0 <= (smallerSet.size() - largerSet.size()) <= 1

        // Technically, size of smallerSet is not more larger than largerSet's by 1.
        // Because every time the unbalanced situation happens, following statements
        // will be executed to maintain the balance

        if (smallerSet.size() - largerSet.size() > 1) {
            largerSet.add(smallerSet.pollFirst());
        }

        // Similar with above logic

        if (smallerSet.size() < largerSet.size()) {
            smallerSet.add(largerSet.pollFirst());
        }
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""