Java Easy To Understand Two Priority Queues


  • 0
    J

    Using two Queues, the idea is easy to understand. The code is clean, I just modified the code for "Find Median from Data Stream".

    public class Solution {

    PriorityQueue<Double> high = new PriorityQueue();
    PriorityQueue<Double> low = new PriorityQueue(Collections.reverseOrder());
    
    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] rst = new double[nums.length - k + 1];
        if (k == 1) {
            for (int i = 0; i < nums.length; i++) {
                rst[i] = (double)nums[i];
            }
        }
        for (int i = 0; i < k; i++) {
            addNum((double)nums[i]);
        }
        rst[0] = findMedian();
        for (int i = 1; i <= nums.length - k; i++) {
            remove((double)nums[i - 1]);
            addNum((double)nums[i + k - 1]);
            rst[i] = findMedian();
        }
        return rst;
    }
    
    public void addNum(double num) {
        low.offer(num);
        high.offer(low.poll());
        if (low.size() < high.size()) {
            low.offer(high.poll());
        }
    }
    
    public double findMedian() {
        if (low.size() == high.size()) {
            return (low.peek() + high.peek()) / 2.0;
        }
        else return low.peek();
    }
    
    public void remove(double num) {
        if (num <= findMedian()) {
            low.remove(num);
        }
        else {
            high.remove(num);
        }
        if (low.size() < high.size()) {
            low.offer(high.poll());
        }
        else if (low.size() > high.size()) {
            high.offer(low.poll());
        }
    }
    

    }


Log in to reply
 

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