Java Using Two PriorityQueues To Conquer


  • 1

    Just maintain two priority queues maxHeap and minHeap, maxHeap to store the less half, and minHeap larger half, the median should be easily got maxHeap.peak if k % 2 == 1 else average of maxHeap.peek() and minHeap.peek().

    import java.util.Collections;
    import java.util.PriorityQueue;
    public class Solution {
        public double[] medianSlidingWindow(int[] nums, int k) {
            if(nums==null || nums.length==0 || k==0) return new double[0];
            double[] res = new double[nums.length - k + 1];
            PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, Collections.reverseOrder());
            PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(k);
            int idx = 0;
            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){
                    if (k % 2 == 1) {
                        res[idx] = (1.0 * maxHeap.peek());
                    }
                    else {
                        res[idx] = (maxHeap.peek()/2.0 + minHeap.peek()  / 2.0);
                    }
                    idx += 1;
                    int toRemove = nums[i-k+1];
                    if(toRemove<=maxHeap.peek()){
                        maxHeap.remove(toRemove);
                    }else{
                        minHeap.remove(toRemove);
                    }
                    if(minHeap.size() > maxHeap.size()){
                        maxHeap.add(minHeap.poll());
                    }
                    if(maxHeap.size() > minHeap.size()+1){
                        minHeap.add(maxHeap.poll());
                    }
                }
            }
            
            return res;
        }
    }
    

  • 0
    N

    http://stackoverflow.com/questions/12719066/priority-queue-remove-complexity-time

    Java's PriorityQueue remove(Object o) method complexity is O(n) not O(logn)


Log in to reply
 

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