跳至主要內容

解决用Arrays.sort()排序整数溢出问题、Arrays.sort()排序中Lambda表达式和Integer.compare()的区别、最少的数量引爆气球有一组测试用例不通过的情况

red-velet原创Bug记录约 927 字大约 3 分钟

解决用Arrays.sort()排序整数溢出问题、Arrays.sort()排序中Lambda表达式和Integer.compare()的区别、最少的数量引爆气球有一组测试用例不通过的情况

背景：

  • 做题时碰到了如下情况，使用Arrays.sort()进行排序后，有一组测试不通过，切换另一种传入排序的策略就通过。
问题描述1
问题描述1
问题描述2
问题描述2
问题描述3
问题描述3
  • 发现有点不对劲的地方：这组测试用例的数据非常极端：要不非常大，或者非常小

发现问题：Integer.compare()和lambda表达式-匿名内部类排序的区别：

Integer.compare()的源码：

  • 其注释很详细：
    • 如果 x == y，则返回值为 0；
    • 如果 x < y，则返回一个小于 0 的值，此处是-1；
    • 如果 x > y，则返回一个大于 0 的值，此处是1。
源码展示
源码展示

lambda表达式 -匿名内部类写法：

  • 返回的是两个差值
  • 这里直接使用了 o1[0] - o2[0] 进行比较，如果 o1[0] 和 o2[0] 的值很大，有可能在计算差值的时候发生整数溢出，导致比较结果不准确，可能会有整数溢出的问题。
Arrays.sort(points, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[0] - o2[0];
    }
});

例如：让我们来看一个可能导致整数溢出问题

假设有以下两个数组：

int[] a = { Integer.MAX_VALUE, 0 };
int[] b = { Integer.MIN_VALUE, 0 };

这两个数组分别代表了两个区间，a 区间的左边界很大，b 区间的左边界很小。

在第一个实现中，使用 Lambda 表达式：

Arrays.sort(points, (x, y) -> Integer.compare(x[0], y[0]));

在这里，Integer.compare(x[0], y[0]) 会返回 -1，因为 a[0] 比 b[0] 大。

而在第二个实现中，使用匿名内部类：

Arrays.sort(points, new Comparator<int[]>() {
    @Override
    public int compare(int[] x, int[] y) {
        return x[0] - y[0];
    }
});

在这里，x[0] - y[0] 的结果是一个非常大的正整数，因为 a[0] 是 Integer.MAX_VALUE，b[0] 是 Integer.MIN_VALUE，所以 x[0] - y[0] 会溢出，导致比较的结果不准确。

为了解决这个问题，可以将第二个实现中的比较方式修改为使用 Integer.compare：

Arrays.sort(points, new Comparator<int[]>() {
    @Override
    public int compare(int[] x, int[] y) {
        return Integer.compare(x[0], y[0]);
    }
});

这样就能够避免整数溢出问题，确保比较结果的准确性。

Tip：什么是整数溢出：

整数溢出是指在进行整数运算时，结果的值超过了该数据类型所能表示的范围，导致数据溢出到另一端。在 Java 中，整数溢出会导致结果不准确，因为超出表示范围的部分会被丢弃，而只保留有效的位。

在上面的例子中，我们来看一下整数溢出是如何发生的：

int[] a = { Integer.MAX_VALUE, 0 };
int[] b = { Integer.MIN_VALUE, 0 };

在这里，a[0] 是 Integer.MAX_VALUE，它表示的是 2147483647。而 b[0] 是 Integer.MIN_VALUE，它表示的是 -2147483648。

当我们使用 x[0] - y[0] 进行比较时，实际上是在计算 2147483647 - (-2147483648)。这个结果超出了 int 数据类型的表示范围，它只能表示 -2147483648 到 2147483647 之间的整数。

在计算过程中，超出范围的部分会导致整数溢出，最终的结果不是我们期望的 2147483647 - (-2147483648)，而是一个负数。这样的结果会影响到排序的正确性，因为实际上我们期望 a[0] 大于 b[0]。

使用 Integer.compare(x[0], y[0]) 能够避免这个问题，因为它使用了安全的方式比较两个整数，不会发生整数溢出。