Easy Understand Java Two PriorityQueues


  • 0
    W
        public class Solution {
        PriorityQueue<Long> min = new PriorityQueue<>();
        PriorityQueue<Long> max = new PriorityQueue<>();
    
        public double[] medianSlidingWindow(int[] nums, int k) {
            double[] result = new double[nums.length - k + 1];
            for (int i = 0; i < nums.length; i++) {
                if (i >= k) {
                    double median = findMedian();
                    result[i - k] = median;
    
                    if (nums[i - k] >= median) {
                        max.remove((long) nums[i - k]);
                    } else {
                        min.remove(-(long) nums[i - k]);
                    }
                }
                addNum(nums[i]);
            }
            result[result.length - 1] = findMedian();
            return result;
        }
    
        public void addNum(int num) {
            max.add((long) num);
            min.add(-max.poll());
            if (max.size() < min.size()) {
                max.add(-min.poll());
            }
        }
    
        public double findMedian() {
            if (max.size() != min.size()) {
                return max.peek();
            } else {
                return (max.peek() - min.peek()) / 2.0;
            }
        }
    }
    

    reference
    https://discuss.leetcode.com/topic/27521/short-simple-java-c-python-o-log-n-o-1


Log in to reply
 

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