优先队列解决LC 480

来源:6-6 优先队列

讲武德的年轻人

2022-07-09

bobo老师,我有一个java语法问题请教,是在做lc 480 sliding window median时遇到的,以下为代码:

问题出在第7-10行。我之前写的PQ的定义是第8,9行,用lambda定义pq的排序,但是有2个case不能通过,貌似有整数越界的问题。但是参考了下别人代码,写成第7,8行就没问题了。请问这是何种原因?我查了以下,貌似没有查到相关内容。。谢谢您!

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        
        int n = nums.length;
        double[] res = new double[n - k + 1];
        
        PriorityQueue<Integer> small = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        PriorityQueue<Integer> large = new PriorityQueue<>((a, b) -> Integer.compare(a, b));
        // PriorityQueue<Integer> large = new PriorityQueue<>();
        // PriorityQueue<Integer> small = new PriorityQueue<>((a, b) -> (b - a));
        
        for (int i = 0; i < k; i++)
            large.offer(nums[i]);
        
        for (int i = 0; i < k / 2; i++)
            small.offer(large.poll());
        
        res[0] = getMedian(large, small);
        
        for (int i = k; i < n; i++) {
            
            int num = nums[i];
            int del = nums[i - k];
            
            if (num >= large.peek())
                large.offer(num);
            else
                small.offer(num);
            
            if (del >= large.peek())
                large.remove(del);
            else
                small.remove(del);
            
            adjust(large, small);
            
            res[i - k + 1] = getMedian(large, small);
        }
        
        return res;
        
      
    }
    
   private double getMedian(PriorityQueue<Integer> large,PriorityQueue<Integer> small) {
       
       if (large.size() == small.size())
           return (large.peek() / 2.0) + small.peek() / 2.0;
       
       if (large.size() == small.size() + 1)
           return large.peek() * 1.0;
       
       return 1.0;
   }
    
    private void adjust(PriorityQueue<Integer> large,PriorityQueue<Integer> small)  {
        
        while (large.size() < small.size())
            large.offer(small.poll());
        
        while (large.size() > small.size() + 1)
            small.offer(large.poll());
    }
    
    
}


写回答

1回答

liuyubobobo

2022-07-10

Java 的 Integer compre 的实现类似这样,没有加减运算,所以不会整形溢出:

public int compareTo(Integer anotherInteger) {    
    int thisVal = this.value;    
    int anotherVal = anotherInteger.value;    
    return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
}


比如 b = -2e9, a = 2e9,a 和 b 都在 int 范围内,但是 b - a = -4e9,超出了 int 的范围,整形溢出。


继续加油!:)

0
0

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程