easy to understand, clean Java code


  • 0
    Y

    This solution is based on the idea offered by
    https://discuss.leetcode.com/topic/27521/short-simple-java-c-python-o-log-n-o-1/2

    public class Solution {
        PriorityQueue<Double> small = new PriorityQueue<>();
        PriorityQueue<Double> large = new PriorityQueue<>();
    
        void add(double num) {
            large.offer(num);
            small.offer(-large.poll());
            // large's size is always >= small's size
            if (large.size() < small.size()) {
                large.offer(-small.poll());
            }
        }
    
        double getMedian() {
            return large.size() > small.size() ?
                    large.peek() : (large.peek() - small.peek()) / 2.0;
        }
    
        void remove(double num) {
            if (num < getMedian()) {
                small.remove(-num);
            } else {
                large.remove(num);
                if (small.size() > large.size()) {
                    large.offer(-small.poll());
                }
            }
        }
    
        public double[] medianSlidingWindow(int[] nums, int k) {
            int n = nums.length - k + 1;
            double[] result = new double[n];
    
            for (int i = 0; i <= nums.length; i++) {
                if (i >= k) {
                    result[i-k] = getMedian();
                    remove((double)nums[i-k]);
                }
                if (i < nums.length) {
            	    add((double)nums[i]);
                }
            }
    
            return result;
        }
    }
    

Log in to reply
 

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