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

Hash Heap

跟lintcode 81. Data Stream Median 的思路一样，用max heap 和 min heap 保存所求区间的前半段和后半段, 不同的是, 因为加了sliding window的限定，所以要删除超出windows的元素。一般的heap的删除是O(n)的时间复杂度，所以要用Hash Heap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
    ArrayList<Integer> ans = new ArrayList<>();
    PriorityQueue<Integer> min = new PriorityQueue<>();
    PriorityQueue<Integer> max = new PriorityQueue<>(10, Collections.reverseOrder());
    for (int i = 0; i < nums.length; i++) {
        int n = nums[i];
        if (i > k - 1) {
            int remove = nums[i - k];
            if (max.peek() >= remove) {
                max.remove(remove);
            } else {
                min.remove(remove);
            }
        }
        max.offer(n);
        min.offer(max.poll());
        while (min.size() > max.size()) {
            max.offer(min.poll());
        }
        if (i >= k - 1)
            ans.add(max.peek());
    }
    return ans;
}