当我试图使用比较器根据元素的频率对它们进行排序时，我得到了这样的错误:Compavision违反了它的一般合同

Question

所以我试图用比较器解决一个关于根据元素频率对元素进行排序的问题，结果得到了这个错误消息。问题是：

给定一个整数数组A[]，根据元素的频率对数组进行排序。也就是说，频率较高的元素优先。若两个元素的频率相同，那个么先出现较小的数字。

我已经在下面附上了代码和相应的错误消息。

错误消息：

Runtime Error:
Runtime ErrorException in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeHi(TimSort.java:899)
at java.util.TimSort.mergeAt(TimSort.java:516)
at java.util.TimSort.mergeForceCollapse(TimSort.java:457)
at java.util.TimSort.sort(TimSort.java:254)
at java.util.Arrays.sort(Arrays.java:1512)
at java.util.ArrayList.sort(ArrayList.java:1460)
at java.util.Collections.sort(Collections.java:175)
at Main.sortEleByFreq(File.java:50)
at Main.main(File.java:30)

代码：

import java.util.*;
class Main 
{
static class pair
{
int val;
int freq;
pair(int val,int freq)
{
this.val = val;
this.freq=freq;
}
}
public static void main (String[] args) 
{
Scanner sc = new Scanner(System.in);
int t =sc.nextInt();
while(t-->0)
{   
int n =sc.nextInt();
int a[] = new int[n];
for(int i =0 ;i <n ; i++)
{
a[i]= sc.nextInt();
}
sortEleByFreq(a,n);
}
}
static void sortEleByFreq(int a[],int n)
{
Arrays.sort(a);
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<n;i++)
{
if(map.containsKey(a[i]))
map.put(a[i],map.get(a[i])+1);
else
map.put(a[i],1);
}
ArrayList<pair> res = new ArrayList<>();
for(int i=0;i<n;i++)
res.add(new pair(a[i],map.get(a[i])));
Collections.sort(res,new CustomSort());
StringBuilder sb = new StringBuilder();
for(int i=0;i<n;i++)
sb.append(res.get(i).val+" ");
System.out.println(sb);
}
static class CustomSort implements Comparator<pair>
{
public int compare(pair p1,pair p2)
{
if(p1.freq<p2.freq||p1.freq==p2.freq && p1.val>p2.val)
return 1;
return -1;
}
}
}

因此，我将元素的频率和值存储为一对，然后使用比较器对其进行排序

Answer 1

在p1.val == p2.val、的情况下，您也需要返回0

static class CustomSort implements Comparator<pair>
{
public int compare(pair p1,pair p2)
{
if(p1.freq<p2.freq||p1.freq==p2.freq && p1.val>p2.val)
return 1;
if (p1.val == p2.val)
return 0;
return -1;
}
}

Answer 2

您的Comparator应该处理所有的案例，而您现在还没有，以下是如何：

• 处理p1.freq < p2.freq和p1.freq > p2.freq

• 如果不相等，则在val字段上排序

static class CustomSort implements Comparator<pair>{
public int compare(pair p1,pair p2){
if(p1.freq < p2.freq)
return 1;
if(p1.freq > p2.freq)
return -1;
return Integer.compare(p1.val, p2.val);
}
}