优先队列解决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回答
-
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 的范围,整形溢出。
继续加油!:)
00
相似问题