LintCode 360 - Sliding Window Median

Related: LeetCode 480 - Sliding Window Median
(360) Sliding Window Median

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

+

    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;
    }




http://shibaili.blogspot.com/2015/08/day-119-239-sliding-window-maximum.html

1. How about using a data structure such as deque (double-ended queue)?
2. The queue size need not be the same as the window’s size.
3. Remove redundant elements and the queue should store only elements that need to be considered.

http://articles.leetcode.com/2011/01/sliding-window-maximum.html
compare function的写法跟用法O(NlgN)

class Cmp{

public:

    bool operator() (pair<int,int> &p1,pair<int,int> &p2) {

        return p1.second < p2.second;

    } 

};

class Solution {

public:

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        if (k == 0) {

            vector<int> rt;

            return rt;

        }

        if (k == 1) return nums;

        vector<int> rt(nums.size() - k + 1);

        priority_queue<pair<int,int>,vector<pair<int,int>>,Cmp> heap; // index, value

        for (int i = 0; i < k - 1; i++) {

            heap.push(make_pair(i,nums[i]));

        }

         

        for (int i = k - 1; i < nums.size(); i++) {

            heap.push(make_pair(i,nums[i]));

            while (heap.top().first < i - k + 1) {

                heap.pop();

            }

            rt[i - k + 1] = heap.top().second;

        }

         

        return rt;

    }

O(n) 

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int> rt;

        deque<int> que;

        for (int i = 0; i < k - 1; i++) {

            while (!que.empty() && nums[i] >= nums[que.back()]) {

                que.pop_back();

            }

            que.push_back(i);

        }

         

        for (int i = k - 1; i < nums.size(); i++) {

            while (!que.empty() && nums[i] >= nums[que.back()]) {

                que.pop_back();

            }

            if (!que.empty() && que.front() < i - k + 1) {

                que.pop_front();

            }

            que.push_back(i);

            rt.push_back(nums[que.front()]);

        }

         

        return rt;

    }

http://www.jiuzhang.com/solutions/sliding-window-median/\

    public List<Integer> medianSlidingWindow(int[] nums, int k) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return new ArrayList<Integer>();
        }
        List<Integer> res = new ArrayList<>();
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer> () {
                public int compare(Integer x, Integer y) {
                    return y - x;
                }
            });
        
        int curMedian;
        if (k > 1) {
            maxHeap.add(nums[0]);
            for (int i = 1; i < k - 1; i++) {
                int x = maxHeap.peek();
                if (nums[i] <= x) {
                    maxHeap.add(nums[i]);
                } else {
                    minHeap.add(nums[i]);
                }
            }
            curMedian = maxHeap.peek();
        } else {
            curMedian = 0;
        }
        
        for (int i = k - 1; i < nums.length; i++) {
            if (nums[i] <= curMedian) {
                maxHeap.add(nums[i]);
            } else {
                minHeap.add(nums[i]);
            }
            while (maxHeap.size() > minHeap.size()+1) {
                minHeap.add(maxHeap.poll());
            }
            while (maxHeap.size() < minHeap.size()) {
                maxHeap.add(minHeap.poll());
            }
            curMedian = maxHeap.peek();
            res.add(curMedian);
            if (nums[i - k + 1] <= curMedian) {
                maxHeap.remove(nums[i - k + 1]);
            } else {
                minHeap.remove(nums[i - k + 1]);
            }
        }
        
        return res;
    }

    vector<int> medianSlidingWindow(vector<int> &nums, int k) {
        // write your code here
        vector<int> result;
        int n = nums.size();
        if (n == 0)
            return result;

        multiset<int> max, min;
        for (int i = 0; i < k; ++i)
            max.insert(nums[i]);

        for (int i = 0; i < k/2; ++i) {
            min.insert(*max.rbegin());
            max.erase(max.lower_bound(*max.rbegin()));
        }

        for (int i = k; i < n; ++i) {
            result.push_back(*max.rbegin());
            if (max.find(nums[i-k]) != max.end()) {
                max.erase(max.find(nums[i-k]));
                max.insert(nums[i]);
            } else {
                min.erase(min.find(nums[i-k]));
                min.insert(nums[i]);
            }
            if (max.size() > 0 && min.size() > 0 && *max.rbegin() > *min.begin()) {
                int tmp = *max.rbegin();
                max.erase(max.lower_bound(*max.rbegin()));
                max.insert(*min.begin());
                min.erase(min.begin());
                min.insert(tmp);
            }
        }
        result.push_back(*max.rbegin());

        return result;
    }

https://gist.github.com/gcrfelix/337a66b78064c8fe2a43
public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
    // write your code here
    ArrayList<Integer> res = new ArrayList<Integer>();
    if(nums==null || nums.length==0 || k==0) return res;
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, Collections.reverseOrder());
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(k);
 
    for(int i=0; i<nums.length; i++){
        if(maxHeap.isEmpty() || nums[i]<maxHeap.peek()){
            maxHeap.add(nums[i]);
        }else{
            minHeap.add(nums[i]);
        }
     
        if(minHeap.size() > maxHeap.size()){
            maxHeap.add(minHeap.poll());
        }
     
        if(maxHeap.size() > minHeap.size()+1){
            minHeap.add(maxHeap.poll());
        }
     
        if(i>=k-1){
            res.add(maxHeap.peek());
            int toRemove = nums[i-k+1];
            if(toRemove<=maxHeap.peek()){
                maxHeap.remove(toRemove);
            }else{
                minHeap.remove(toRemove);
            }
           // don't need this
            if(minHeap.size() > maxHeap.size()){
                maxHeap.add(minHeap.poll());
            }
            if(maxHeap.size() > minHeap.size()+1){
                minHeap.add(maxHeap.poll());
            }
        }
    }
 
    return res;
}
Read full article from (360) Sliding Window Median