java.lang.IllegalArgumentException:比较方法违反其常规约定java.base/java.util.TimSort.mergeColrapse

Question

class Solution {
    public int[] frequencySort(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i : nums) {
            list.add(i);
        }
        list = fun(list);
        for(int i=0;i<nums.length;i++){
            nums[i] = list.get(i);
        }
        return nums;
    }
    
    public ArrayList<Integer> fun(ArrayList<Integer> list){
        Map<Integer,Integer> map = new HashMap<>();
        
        list.forEach(i -> {
            map.put(i,map.getOrDefault(i,0)+1);
        });
        
        Collections.sort(list,(n1,n2) -> {
            int freq1 = map.get(n1);
            int freq2 = map.get(n2);
            
            if(freq1!=freq2){
                return freq1-freq2;
                // if(freq1>freq2){
                //     return 1;
                // }
                // return -1;
            }
            return n2-n1;
            //if(n1>=n2){
            //   return -1;
            //}
           // return 1;
            
        } );
        return list;
    }
}

//sample input : nums = [2,3,1,3,2]
//output : [1,3,3,2,2]

在fun方法中，在Collections.sort()中，我根据频率的递增顺序对数组进行排序，如果两者具有相同的频率，则将它们按值的递增顺序相加。上面的代码工作得很好，我从谷歌得到的，但我自己也写了几乎类似的代码，我已经包括作为注释。这两个代码看起来很相似，但是我的代码(作为注释)只通过了85/150个测试用例，之后我得到了"java.lang.IllegalArgumentException:比较方法违反了它的一般约定！“

我发现了类似的问题，但我不能理解，有人用更简单的术语解释它！

//This block I found in google

if(freq1!=freq2){
    return freq1-freq2;
 }
 return n2-n1;

//Below Block gives "Comparison method violates its general contract"

if(freq1!=freq2){
       if(freq1>freq2){
          return 1;
        }
       return -1;
}
if(n1>=n2){
       return -1;
}
return 1;

Answer 1

由于以下原因，您作为违反合同的示例所给出的最后一个块是错误的。

例如，如果我们有两个元素a = (5, 1)和b = (5, 1)，其中我将每个元素表示为(freq, n)的元组，那么比较a和b将返回-1，指定在排序列表中a必须早于b。但是，如果我们以相反的顺序比较这两个值-- b和a，则给定的示例仍将返回-1，这一次说明b必须早于a。

我认为，在freq和n相等的情况下，显式地处理返回0应该可以修复最后一段代码。