Java solution using two PriorityQueues


  • 0
    H

    The idea is similar to 295.Find Median from Data Stream. I used two priority queues to solve this problem. To avoid max integer value overflow, Long data type is used here.

    class Solution {
        public double[] medianSlidingWindow(int[] nums, int k) {
            PriorityQueue<Long> small = new PriorityQueue<>();
            PriorityQueue<Long> large = new PriorityQueue<>();
            
            double[] res = new double[nums.length - k + 1];
            int m = k / 2;
            for(int i = 0; i < k; i++){
                insert(nums[i], small, large);
            }
            
            res[0] = findMedian(small, large);
            // add tail from index j, remove head at index j-k
            for(int j = k; j < nums.length; j++){
                remove(nums[j - k], small, large);
                insert(nums[j], small, large);
                res[j - k + 1] = findMedian(small, large);
            }
            return res;
        }
        
        public void insert(long n, PriorityQueue<Long> small, PriorityQueue<Long> large){
            large.add(n);
            small.add(-large.poll());
            if(large.size() < small.size()){
                large.add(-small.poll());
            }
        }
        public void remove(long n, PriorityQueue<Long> small, PriorityQueue<Long> large){
            if(n < findMedian(small, large)){
                small.remove(-n);
            }
            else{
                large.remove(n);
            }
        }
        public double findMedian(PriorityQueue<Long> small, PriorityQueue<Long> large){
            if(large.size() > small.size()){
                return large.peek() * 1.0;
            }
            else{
                return (large.peek() - small.peek()) / 2.0;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.