"Comparison method violates general contract " 对多维数组进行排序时

Question

我正在使用自定义比较器对二维数组进行排序，在某些情况下出现以下错误：

java.lang.IllegalArgumentException: Comparison method violates its general contract! at line 781, java.base/java.util.TimSort.mergeLo at line 518, java.base/java.util.TimSort.mergeAt at line 448, java.base/java.util.TimSort.mergeCollapse at line 245, java.base/java.util.TimSort.sort at line 1442, java.base/java.util.Arrays.sort

下面是引发此错误的代码：

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new SortComparator());
    }
}

class SortComparator implements Comparator<int[]> {
    public int compare(int []a, int []b) {
        if(a[0] < b[0]) {
            return -1;
        } else if(a[0] > b[0]) {
            return 1;
        } else {
            if(a[1] < b[1]) {
                return -1;
            } else {
                return 1;
            }
        }
    }
}

尽管当我使用 SortComparator class 的以下实现时，一切正常：

class SortComparator implements Comparator<int[]> {
    public int compare(int []a, int []b) {
        if(a[0] < b[0]) {
            return -1;
        } else if(a[0] > b[0]) {
            return 1;
        } else {
            if(a[1] < b[1]) {
                return -1;
            } else if(a[1]> b[1]) {
                return 1;
            } else {
                return 0;
            }
        }
    }
}

我能知道 SortComparator 的首次执行抛出错误的原因吗？

Answer 1

问题是您的第一个 SortComparator 实现永远无法 return 0.

因此 SortComparator.compare(a, a) 永远不会 return 0 因为它是 Comparator 实施的“总合同”所要求的。

事实上，SortComparator.compare(a, a)会return1。

实际合同在javadoc。它说的是：

The notation sgn(expression) designates¹ the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero or positive.

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

[...]

当 x 和 y 是同一个对象时，sgn(compare(x, y)) == -sgn(compare(y, x)) 可以为真的唯一方法是如果 -sgn(compare(x, x)) 对于所有 x 都是零。

^{1 - 挑剔：我认为他们应该在这里使用“表示”而不是“指定”这个词。}

"Comparison method violates general contract " 对多维数组进行排序时

"Comparison method violates general contract " while sorting multi dimensional array

java

arrays

sorting

comparator