Sliding Window Median 360

Question

Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

Example

For array [1,2,7,8,5], moving window size k = 3. return [2,7,7]

At first the window is at the start of the array like this

[ | 1,2,7 | ,8,5] , return the median 2;

then the window move one step forward.

[1, | 2,7,8 | ,5], return the median 7;

then the window move one step forward again.

[1,2, | 7,8,5 | ], return the median 7;

Challenge

O(nlog(n)) time

Solution

这道题和Data Stream Median类似，也是寻找动态数组的media，因此也可以用maxheap＋minheap来解。随着窗口的移动，每次先加入一个新元素，再删去一个旧元素，再使两个heap中元素数量平衡即可。

1. 用一个最大堆来记录较小一半的元素，一个最小堆来记录较大一半的元素。

2. 先初始化最初的窗口里的k个元素。将元素加入最大堆，若为奇数次，则比较最大堆堆顶和最小堆堆顶元素大小，若最大堆堆顶元素大于和最小堆堆顶元素，则交换两个堆顶元素，若为偶数次，则将最大堆堆顶元素加入最小堆。

3. 然后开始移动窗口，先将新元素加入，若比原median小，则加入最大堆，反之则加入最小堆。然后删除窗口最前面的一个元素。

4. 然后调整最大堆和最小堆的大小。根据k值可以分两种情况讨论：

   1）若k为偶数，则需要最大堆中元素和最小堆中元素数量相等

   2）若k为奇数，则需要最大堆中元素比最小堆中元素多1个

5. 此时最大堆的堆顶元素即为此时窗口元素的median

代码如下：

public class Solution {
    /**
     * @param nums: A list of integers.
     * @return: The median of the element inside the window at each moving.
     */
    class Node{
        int val;
        int index;
        public Node(int val, int index){
            this.val = val;
            this.index = index;
        }
    }
    public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
        // write your code here
        ArrayList<Integer> res = new ArrayList<Integer>();

        if(nums == null || nums.length < k || k < 1){
            return res;
        }

        Queue<Integer> max = new PriorityQueue<Integer>(1, new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                return b - a;
            }
        });

        Queue<Integer> min = new PriorityQueue<Integer>(1, new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                return a - b;
            }
        });

        //初始化第1个窗口
        for(int i = 0; i < k; i++){
            max.offer(nums[i]);
            if(i % 2 == 0){
                if(min.size() != 0 && max.peek() > min.peek()){
                    int maxTop = max.poll();
                    int minTop = min.poll();
                    min.offer(maxTop);
                    max.offer(minTop);
                }
            }else{
                min.offer(max.poll());
            }
        }
        res.add(max.peek());

        for(int i = k; i < nums.length; i++){
            //add
           if(nums[i] > max.peek()){
               min.offer(nums[i]);
           }else{
               max.offer(nums[i]);
           }

           //delete，可以用HashHeap优化
           if(max.contains(nums[i - k])){
               max.remove(nums[i - k]);
           }else{
               min.remove(nums[i - k]);
           }

           if(k % 2 == 0 && max.size() != min.size()){
               if(max.size() < min.size()){
                   while(max.size() != min.size()){
                       max.offer(min.poll());
                   }
               }else{
                   while(max.size() != min.size()){
                       min.offer(max.poll());
                   }
               }
           }

           if(k % 2 == 1 && max.size() != min.size() + 1){
               if(max.size() < min.size()){
                   while(max.size() != min.size() + 1){
                       max.offer(min.poll());
                   }
               }else{
                   while(max.size() != min.size() + 1){
                       min.offer(max.poll());
                   }
               }
           }

            res.add(max.peek());
        }

        return res;
    }
}