虽然尝试使用比较器根据元素的频率对排序元素进行排序，但我收到此错误：比较违反了它的总协定

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);
    }
}