Отсортируйте список строк, в которых строка содержит 4 числа, с помощью компаратора - PullRequest
Новая
       72

Отсортируйте список строк, в которых строка содержит 4 числа, с помощью компаратора

0 голосов
/ 05 августа 2020

Я пытаюсь решить вопрос с 4 суммой структур данных и алгоритмов, который есть на Geeks for Geeks: https://practice.geeksforgeeks.org/problems/find-all-four-sum-numbers/0

Вот мое решение: 

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
     public static void solve(int[] a,int n,int k)
     {
         Arrays.sort(a);
         HashMap<Integer,List<int[]>> hs = new HashMap<>();
         HashSet<String> set = new HashSet<>();
         List<String> ss = new ArrayList<>();
         boolean flag=false;
         for(int i=0;i<n-1;i++)
         {
             for(int j=i+1;j<n;j++)
             {
                 int sum = a[i]+a[j];
                 if(hs.containsKey(k-sum))
                 {
                     List<int[]> indexes = hs.get(k-sum);
                      
                    for(int[] index : indexes)
                    {
                        int i1 = index[0];
                        int i2 = index[1];
                        if(i2<i && i1!=i && i1!=j && i2!=i && i2!=j)
                        {
                            
                            String s = new String(""+a[index[0]]+" "+a[index[1]]+" "+a[i]+" "+a[j]+" $");
                            flag=true;
                            if(!set.contains(s))
                                ss.add(s);
                            set.add(s);    
                        }
                    }
                 }
                 List<int[]> temp = hs.getOrDefault(sum,new ArrayList<>());
                 temp.add(new int[]{i,j});
                 hs.put(sum,temp);
             }
         }
         if(!flag)
         System.out.print(-1);
         else
         {
             Collections.sort(ss,(String a1,String b1)->{
                 String[] st1 = a1.split(" ");
                 String[] st2 = b1.split(" ");
                //  if(a1.compareTo(b1)==0)
                //     return 0;
                 for(int i=0;i<st1.length;i++)
                 {
                     if(st1[i].compareTo(st2[i])>0)
                     {
                         return 1;
                     }
                 }
                 return -1;
             });
             for(String s1 : ss)
                System.out.print(s1);
         }
         System.out.println();
     }
     
     
    public static void main (String[] args)
     {
     Scanner sc = new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0)
        {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int[] a = new int[n];
            for(int i=0;i<n;i++)
                a[i]=sc.nextInt();
            solve(a,n,k);
        }
     }
}

Для ответа требуется, чтобы строки были отсортированы, т.е. все уникальные числа должны быть в порядке возрастания, я создал список строк, но я не могу отсортировать их в порядке возрастания,

Например:

Ввод: 27 179 88 84 3 51 54 99 32 60 76 68 39 12 26 86 94 39 95 70 34 78 67 1 97 2 17 92 52

Его правильный вывод: 1 2 84 92 $ 1 3 76 99 $ 1 3 78 97 $ 1 12 67 99 $ 1 12 78 88 $ 1 17 67 94 $ 1 26 60 92 $ 1 26 68 84 $ 1 32 51 95 $ 1 32 52 94 $ 1 32 54 92 $ 1 32 60 86 $ 1 32 68 78 $ 1 32 70 76 $ 1 34 52 92 $ 1 34 60 84 $ 1 34 68 76 $ 1 39 51 88 $ 1 51 60 67 $ 2 3 86 88 $ 2 12 68 97 $ 2 12 70 95 $ 2 17 68 92 $ 2 17 76 84 $ 2 26 52 99 $ 2 26 54 97 $ 2 26 67 84 $ 2 32 51 94 $ 2 32 67 78 $ 2 34 51 92 $ 2 34 67 76 $ 2 39 39 99 $ 2 39 52 86 $ 2 39 54 84 $ 2 39 60 78 $ 2 39 68 70 $ 3 12 67 97 $ 3 12 70 94 $ 3 12 76 88 $ 3 12 78 86 $ 3 17 60 99 $ 3 17 67 92 $ 3 26 51 99 $ 3 32 52 92 $ 3 32 60 84 $ 3 32 68 76 $ 3 34 54 88 $ 3 39 51 86 $ 3 39 67 70 $ 3 52 54 70 $ .........

Мой вывод кода: Ваш вывод: 12 34 39 94 $ 17 26 39 97 $ 34 39 39 67 $ 17 39 39 84 $ 2 39 39 99 $ 26 34 51 68 $ 26 32 51 70 $ 12 32 51 84 $ 3 39 51 86 $ 1 39 51 88 $ 2 34 51 92 $ 2 32 51 94 $ 1 32 51 95 $ 12 17 51 99 $ 3 26 51 99 $ 34 39 52 54 $ 26 34 52 67 $ ......

Как это сделать? используя компаратор, я написал несколько логинов компаратора, но он либо дает неправильный вывод, либо дает какую-то ошибку: 

Runtime Error:
Runtime ErrorException in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.base/java.util.TimSort.mergeLo(TimSort.java:781)
    at java.base/java.util.TimSort.mergeAt(TimSort.java:518)
    at java.base/java.util.TimSort.mergeCollapse(TimSort.java:448)
    at java.base/java.util.TimSort.sort(TimSort.java:245)
    at java.base/java.util.Arrays.sort(Arrays.java:1515)
    at java.base/java.util.ArrayList.sort(ArrayList.java:1749)
    at java.base/java.util.Collections.sort(Collections.java:179)
    at GFG.solve(File.java:46)
    at GFG.main(File.java:78)

Пожалуйста, помогите,

Спасибо

1 Ответ

1 голос
/ 05 августа 2020

При реализации Comparator<T> (что вы делаете с лямбда-выражением в Collections.sort()) вы должны следовать нескольким правилам. Одно из правил состоит в том, что оператор должен возвращать -1, если первый должен быть перед вторым элементом, 1, если первый должен быть после второго элемента, или 0, если они могут появляться в любом порядке. Поскольку вы не возвращаете 0, это правило нарушается.

Второе правило, нарушаемое вашей реализацией, заключается в том, что compare() метод должен быть транзитивным , то есть если compare(A, B) == 0 и compare(B, C) == 0, затем compare(A, C) == 0. Алгоритмы сортировки могут полагаться на истинность этого правила, что является вероятной причиной появления IllegalArgumentException. Для получения дополнительной информации о том, как правильно реализовать Comparator, проверьте JavaDo c.

...