2

看看这段代码

   class StringComparator implements Comparator<String> {

     @Override
     public int compare(String a, String b) {
         if (a.length() == b.length()) {
             return b.compareTo(a);
         } else {
             String ab = a + b;
             String ba = b + a;
             return ba.compareTo(ab);
         }
     }
 }

ba.compareTo(ab) 有效，但 ab.compareTo(ba) 失败。它抛出一个 IllegalArgumentException 引用违反比较器合同。我相信这是因为传递性属性不满足。有人可以解释一下 Java 在 Strings 的情况下如何使用传递性属性吗？这与 Timsort 的工作方式有什么关系吗？

编辑：这是我在 Leetcode 在线法官上遇到的错误

Runtime Error Message:
                Line 32: java.lang.IllegalArgumentException: Comparison method violates its general contract!




              Last executed input:
                [7286,155,351,6059,9686,2668,9551,5410,7182,170,3746,3095,8139,2587,2351,2341,2038,3956,6034,4071,9473,281,9306,8746,7954,8937,7855,3938,9737,2455,4344,2986,8968,1072,2442,7191,9106,4236,2768,5214,7541,329,7530,9068,9644,3539,5177,5332,2065,8245,7494,8454,604,4632,1745,301,3412,1569,8637,7840,7752,9536,1023,4841,1286,6489,8459,2725,8021,5026,7058,4540,9892,5344,1205,4363,959,9729,9225,9733,8417,9873,3721,1434,5136,6111,6189,780,4741,2670,2457,5424,1040,3746,1229,8568,3636,1546,2553,575]

同样，当我使用 ba.compareTo(ab) 时，我没有收到此错误。一世

4

2 回答 2

1

是的，如果并且长度不同，您compare似乎不尊重传递属性。ab

这是Comparator.compare(a,b) 合约，请参阅有关传递性的粗体部分：

比较它的两个参数的顺序。返回负整数、零或正整数，因为第一个参数小于、等于或大于第二个。在前面的描述中，符号sgn(expression)表示数学符号函数，它被定义为根据表达式的值是负数、零还是正数返回-1、0或1之一。

实现者必须确保所有 x 和 y 的 sgn(compare(x, y)) == -sgn(compare(y, x))。（这意味着当且仅当 compare(y, x) 抛出异常时 compare(x, y) 必须抛出异常。）

实现者还必须确保关系是可传递的： ((compare(x, y)>0) && (compare(y, z)>0)) 意味着 compare(x, z)>0。

最后，实现者必须确保 compare(x, y)==0 意味着所有 z 的 sgn(compare(x, z))==sgn(compare(y, z))。

通常是这样，但并不严格要求 (compare(x, y)==0) == (x.equals(y))。一般来说，任何违反此条件的比较器都应清楚地表明这一事实。推荐的语言是“注意：这个比较器强加了与等于不一致的排序。”

更新：

只是为了添加一个有趣的旁注，您将 Tim 排序称为 Collections.sort() 等应用的排序算法，对于较小的数组（大小低于硬编码阈值），执行简单的合并排序反而。选择是在排序方法的开头进行的，有关更多信息，请参阅 openJDK 源代码。

于 2015-05-12T13:07:04.190 回答
0

假设我们有三个字符串格式的数字 a、b 和 c，并且a | b | c是可以获得的最大结果。

那么我们知道(a | b) > (b | a)和(b | c) > (c | b)。

假设(c | a) > (a | c)（没有传递性），那么我们有：

(c | a | b) > (a | c | b) > (a | b | c). 这个矛盾a | b | c是最大的。

于 2015-11-07T07:01:24.393 回答