正确答案并不超出"整数"的范围，但为什么我的输出为负数？

Question

最近我试图从LeetCode链接中解决一个名为"丑陋数字"的问题。这是描述。

丑陋数是一个素数限制为2、3和5的正整数。给定一个整数n，返回第n个丑陋的数字

这是正确的答案：

public int nthUglyNumber(int n) {
if (n < 7) return n;
PriorityQueue<Long> heap = new PriorityQueue<>();
Set<Long> set = new HashSet<>();
heap.add(1L);
long res = 1;
for (int i = 0; i<n; i++) {
res = heap.poll();
long res_2 = res*2;
long res_3 = res*3;
long res_5 = res*5;
if (!set.contains(res_2)) {
set.add(res_2);
heap.add(res_2);
}
if (!set.contains(res_3)) {
set.add(res_3);
heap.add(res_3);
}
if (!set.contains(res_5)) {
set.add(res_5);
heap.add(res_5);
}
}
return (int) res;
}

这是我的答案：

public int nthUglyNumber(int n) {
if (n < 7) return n;
PriorityQueue<Integer> heap = new PriorityQueue<>();
Set<Integer> set = new HashSet<>();
heap.add(1);
int res = 1;
for (int i = 0; i < n; i++) {
res = heap.poll();
int res_2 = res * 2;
int res_3 = res * 3;
int res_5 = res * 5;
if (!set.contains(res_2)) {
set.add(res_2);
heap.add(res_2);
}
if (!set.contains(res_3)) {
set.add(res_3);
heap.add(res_3);
}
if (!set.contains(res_5)) {
set.add(res_5);
heap.add(res_5);
}
}
return res;
}

正确答案使用类型"Long"，而我使用类型"Integer">

我发现当输入是1407时，右边的输出是536870912，但我的输出是-1425014784。

536870912小于2^32-1，但为什么我的输出是负数？

Answer 1

正确答案是2^29。作为练习的一部分，将其乘以2、3和5。2^29适合int，而2^29 * 5不适合！

尽管如此，你仍然会获得独特性；这些数字落在2^31-2^32的范围内，即如果它们"溢出"，则保持在负空间中。因此，解释并不是说你们有重叠。

存储机制heap是一个PriorityQueue，也就是说，它自然地对自己进行排序。这就是问题所在：那些负数在之前对进行排序。通过溢出，PQ的自然顺序会变得混乱，因为它开始返回较高的数字(因为它们溢出并被视为负数(，而它本应返回较低的数字。

因此，就在你得到第n个数字之前，PQ中有一些负数，所以下一个循环开始返回这些负数，因此你得到了一个负数作为答案。