При попытке сортировки элементов по частоте с помощью компаратора я получил эту ошибку: Сравнение нарушает общий контракт

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

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

Answer 2

Вам также необходимо вернуть 0 в случае p1.val == p2.val,

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