java - 使用 Comparator 对 String 包含 4 个数字的字符串列表进行排序
问题描述
我正在尝试解决 Geeks for Geeks 上关于数据结构和算法的 4 个总和问题: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 7668 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 968 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 9 67 33 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 349 $51 88 2 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)
请帮忙,
谢谢
解决方案
在实现 a 时Comparator<T>
(您使用 lambda 表达式执行此操作Collections.sort()
),您必须遵循一些规则。一条规则是,-1
如果第一个元素必须在第二个元素之前,1
如果第一个元素必须在第二个元素之后,或者0
它们可以以任何顺序出现,则比较器必须返回。由于您不返回0
,因此违反了此规则。
您的实现违反的第二个原则是该compare()
方法必须是可传递的,即 ifcompare(A, B) == 0
和compare(B, C) == 0
then compare(A, C) == 0
。可能排序算法依赖于该规则为真,这可能是IllegalArgumentException
您看到的原因。有关如何正确实施Comparator
检查JavaDoc的更多详细信息。
推荐阅读
- sql - 如何在不同的数据库中查找表列?
- r - 使用 mutate 和 case_when 在 dplyr 中通过双重条件重新编码变量
- sql - 使用每行计算值的 where 子句进行大规模更新?
- linux - 使用 sed 解析 nmap -oG 输出
- memory - Rust 线程之间的内存共享
- kotlin - is there a way to make a function to not return null when lookup from a map
- tensorflow2.0 - Tensorflow2.0 复用层
- c# - @onkeypress 没有得到文本输入框的更新值?
- java - Ehcache 2.10.6 命中统计未增加
- java - LanguageTool Java API 是否有“无用”的依赖关系?