优先队列解决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
相似问题