Sliding Window Median
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. )
ExampleFor 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;
分析：
- 首先，这道题目是一道移动窗口求中位数类的问题，对于动态求中位数的问题，通常我会用heap的模版来处理，即维持两个heap，minheap和maxheap，maxheap来存放所有比中位数小的及相等的数＋中位数，minheap存放所有比中位数大的数；举例说明，当我们的数组是［1，2，7］，这个时候maxheap存放［1，2］，minheap存放［7］，中位数就是maxheap里的最大值，当有新的数进来或者旧的数出去的时候，我们每次都和当前median的大小来比较，决定放入哪个heap，再根据左右两边size的大小进行相应调整，永远满足median是 N/2-th number。
- 选用什么数据结构？因为这里的动态窗口还要求删除被移除窗口的元素，所以我们需要一个数据结构，既能满足heap的性质，又能满足定点删除的性质，于是想到了hashheap！java中TreeSet正好满足。
- 这里有一个tricky的点在于，因为input中的输入点可能是duplicated，直接把数放到treeset中，不能存下duplicated elements，怎么解决？想到了可以构造一个class，同时包含这个element在input array的位置，即id，还包含这个element的value，那么我们将得到unique的object。
代码：
public class Solution {
/**
* @param nums: A list of integers.
* @return: The median of the element inside the window at each moving.
*/
public Node insertNum(Node median, Node currNode, TreeSet<Node> minheap, TreeSet<Node> maxheap){
/* median is put on the maxheap */
if(maxheap.size() == 0 && minheap.size() == 0){
maxheap.add(currNode);
return currNode;
}
if(currNode.val <= median.val){
if(maxheap.size()-minheap.size() < 1){
maxheap.add(currNode);
median = maxheap.last();
}else{
minheap.add(median);
maxheap.remove(median);
maxheap.add(currNode);
median = maxheap.last();
}
}else{
if(maxheap.size() > minheap.size() ){
minheap.add(currNode);
}else{
minheap.add(currNode);
median = minheap.first();
maxheap.add(median);
minheap.remove(median);
}
}
return median;
}
public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
// write your code here
ArrayList<Integer> list = new ArrayList<Integer>();
if(nums.length == 0 || k <= 0 || nums.length < k){
return list;
}
TreeSet<Node> minheap = new TreeSet<Node>();
TreeSet<Node> maxheap = new TreeSet<Node>();
Node median = new Node(0, nums[0]);
maxheap.add(median);
for(int i = 1; i < k; i++){
Node currNode = new Node(i, nums[i]);
median = insertNum(median, currNode, minheap, maxheap);
}
list.add(median.val);
for(int i = k; i < nums.length; i++){
Node currNode = new Node(i, nums[i]);
Node prevNode = new Node(i-k, nums[i-k]);
if (minheap.contains(prevNode)) {
minheap.remove(prevNode);
}
else{
maxheap.remove(prevNode);
}
median = insertNum(median, currNode, minheap, maxheap);
list.add(median.val);
}
return list;
}
}
/* construct node class */
class Node implements Comparable<Node>{
int id;
int val;
Node(int id, int val){
this.id = id;
this.val = val;
}
/* construct compareTo method, to make sure the elements is sorted by val or ID when vals are same */
public int compareTo(Node other){
if(this.val == other.val){
return this.id-other.id;
}
return this.val-other.val;
}
}