按照包含4个数字的字符串,使用比较器来排序字符串列表。

huangapple go评论71阅读模式
英文:

Sort the list of Strings where String contains 4 numbers, by using Comparator

问题

我可以帮你排序字符串列表,使用Comparator来定义自定义排序规则。以下是修改后的代码片段,包括如何使用Comparator来排序字符串列表:

// 导入所需的包
import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
    // ... 你的其他代码 ...

    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();
            List<String> result = solve(a, n, k);
            Collections.sort(result, new Comparator<String>() {
                @Override
                public int compare(String s1, String s2) {
                    String[] st1 = s1.split(" ");
                    String[] st2 = s2.split(" ");
                    for (int i = 0; i < st1.length; i++) {
                        int num1 = Integer.parseInt(st1[i]);
                        int num2 = Integer.parseInt(st2[i]);
                        if (num1 != num2) {
                            return num1 - num2;
                        }
                    }
                    return 0;
                }
            });

            for (String s1 : result)
                System.out.print(s1);
        }
    }
}

这段代码将使用Comparator按照数字的升序对字符串进行排序。希望这能帮助你得到正确的输出结果。如果你有其他问题或需要进一步的帮助,请随时告诉我。

英文:

I am trying to solve the 4 sum question of data structures & algorithms which is on Geeks for Geeks: <https://practice.geeksforgeeks.org/problems/find-all-four-sum-numbers/0>

Here's my solution:

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&lt;Integer,List&lt;int[]&gt;&gt; hs = new HashMap&lt;&gt;();
HashSet&lt;String&gt; set = new HashSet&lt;&gt;();
List&lt;String&gt; ss = new ArrayList&lt;&gt;();
boolean flag=false;
for(int i=0;i&lt;n-1;i++)
{
for(int j=i+1;j&lt;n;j++)
{
int sum = a[i]+a[j];
if(hs.containsKey(k-sum))
{
List&lt;int[]&gt; indexes = hs.get(k-sum);
for(int[] index : indexes)
{
int i1 = index[0];
int i2 = index[1];
if(i2&lt;i &amp;&amp; i1!=i &amp;&amp; i1!=j &amp;&amp; i2!=i &amp;&amp; i2!=j)
{
String s = new String(&quot;&quot;+a[index[0]]+&quot; &quot;+a[index[1]]+&quot; &quot;+a[i]+&quot; &quot;+a[j]+&quot; $&quot;);
flag=true;
if(!set.contains(s))
ss.add(s);
set.add(s);    
}
}
}
List&lt;int[]&gt; temp = hs.getOrDefault(sum,new ArrayList&lt;&gt;());
temp.add(new int[]{i,j});
hs.put(sum,temp);
}
}
if(!flag)
System.out.print(-1);
else
{
Collections.sort(ss,(String a1,String b1)-&gt;{
String[] st1 = a1.split(&quot; &quot;);
String[] st2 = b1.split(&quot; &quot;);
//  if(a1.compareTo(b1)==0)
//     return 0;
for(int i=0;i&lt;st1.length;i++)
{
if(st1[i].compareTo(st2[i])&gt;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--&gt;0)
{
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[n];
for(int i=0;i&lt;n;i++)
a[i]=sc.nextInt();
solve(a,n,k);
}
}
}

The answer requires the strings to be sorted i.e all the unique numbers should be in increasing order,
I have generated a list of Strings but I am unable to sort them in increasing order,

For Ex :

Input:
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

Its Correct output is:
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 $ .........

My Code Output :
Your Output is:
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 $ ......

How can I do that using Comparator, I have written some login of comparator but it is either giving wrong Output or it is giving some sort of error :

Runtime Error:
Runtime ErrorException in thread &quot;main&quot; 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)

Please Help,

Thanks

答案1

得分: 1

在实现Comparator<T>(在Collections.sort()中使用lambda表达式实现)时,必须遵循一些规则。其中一个规则是,如果第一个元素必须位于第二个元素之前,Comparator必须返回-1,如果第一个元素必须位于第二个元素之后,必须返回1,如果它们可以以任意顺序出现,则必须返回0。由于您没有返回0,这个规则被违反了。

您的实现违反的第二个规则是compare()方法必须是可传递的,意思是如果compare(A, B) == 0并且compare(B, C) == 0,那么compare(A, C) == 0。许多排序算法依赖于这个规则的正确性,这可能是您看到IllegalArgumentException的原因。有关如何正确实现Comparator的更多详细信息,请查看JavaDoc

英文:

When implementing a Comparator&lt;T&gt; (which you do with the lambda expression in Collections.sort()) you must follow a few rules. One rule is that the comperator must return -1 if the first must be before the second element, 1 if the first must be after the second element or 0 if they can appear in any order. Since you don't return 0, this rule is violated.

A second tule violated by your implementation is that the compare() method has to be transitive, meaning if compare(A, B) == 0 and compare(B, C) == 0 then compare(A, C) == 0. May sorting algorithms rely on that rule to be true, which is the likely reason for the IllegalArgumentException you see. For more details on how to correctly implement a Comparator check the JavaDoc.

huangapple
  • 本文由 发表于 2020年8月5日 18:16:16
  • 转载请务必保留本文链接:https://go.coder-hub.com/63263025.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定