Java：检查数组的相等性（顺序无关紧要）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10154305/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java: Checking equality of arrays (order doesn't matter)
提问by Popokoko
I have two Stringarrays, let's say:
我有两个String数组，让我们说：
String[] s1 = {"a","b","c"}
String[] s2 = {"c","a","b"}
//these arrays should be equal
//这些数组应该相等
I wanted to check their equality in the "cleanest" way.
我想以“最干净”的方式检查它们的相等性。
I tried using Arrays.equals(s1,s2)but I'm getting a false answer. I guess that this method cares about the elements' order and I don't want that to matter.
我尝试使用，Arrays.equals(s1,s2)但我得到了错误的答案。我猜这个方法关心元素的顺序，我不希望这很重要。
Can you please tell me how can I do that in a nice way?
你能告诉我如何以一种好的方式做到这一点吗？
回答by MoveFast
- Arrays.sort(s1);
- Arrays.sort(s2);
- Arrays.equals(s1,s2);
- Arrays.sort(s1);
- Arrays.sort(s2);
- Arrays.equals(s1,s2);
In case you do not want to modify the original arrays
如果您不想修改原始数组
Arrays.equals( Arrays.sort( Arrays.copyof(s1,s1.length)),
Arrays.sort( Arrays.copyof(s2,s2.length)) );
Arrays.sort() uses an optimized quick sort which is nlog(n) for average but O(n2) in worst case. From the java docs. So the worst case it will O(n2) but practically it will be O(nlogn) for most of the cases.
Arrays.sort() 使用优化的快速排序，平均为 nlog(n)，但在最坏的情况下为 O(n2)。来自 java 文档。所以最坏的情况是 O(n2) 但实际上在大多数情况下它将是 O(nlogn)。
The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.
排序算法是一个经过调整的快速排序，改编自 Jon L. Bentley 和 M. Douglas McIlroy 的“设计排序功能”，软件实践和经验，卷。23(11) P. 1249-1265（1993 年 11 月）。该算法在许多数据集上提供 n*log(n) 性能，导致其他快速排序降级为二次性能。
回答by Lukas Eder
Others have suggested sorting the arrays. But since you're looking for the "cleanest" solution, I think the original arrays shouldn't be touched. Hence:
其他人建议对数组进行排序。但是由于您正在寻找“最干净”的解决方案，我认为不应触及原始数组。因此：
List<String> l1 = new ArrayList<String>(Arrays.asList(s1));
List<String> l2 = new ArrayList<String>(Arrays.asList(s2));
Collections.sort(l1);
Collections.sort(l2);
boolean outcome = l1.equals(l2);
回答by corsiKa
The human way:
人的方式：
Iterate over the first array, checking for the existence of each element in the second array, and then doing the same for the second array on the first array. Time: n^2. Note this method assumes that no element is repeated. If it was, you would have to, for each element you're checking, go back to the beginning and count how many instances of that element there are, (say X), and only count a success as finding the Xth element in the second array. Doing this would eliminate the need for the second check, and left as an exercise to the reader (if you're so inclined, that is.)
迭代第一个数组，检查第二个数组中每个元素是否存在，然后对第一个数组上的第二个数组执行相同的操作。时间：n^2。请注意，此方法假定没有重复元素。如果是，则您必须对要检查的每个元素返回开头并计算该元素有多少个实例（例如 X），并且仅将成功视为找到第 X 个元素第二个数组。这样做将消除第二次检查的需要，并作为练习留给读者（如果您愿意，那就是。）
boolean equal(String[] arr1, String[] arr2) {
if(arr1.length != arr2.length) return false; // obviously
main_loop:
for(int i = 0; i < arr1.length; i++) {
for(int j = 0; j < arr2.length; j++) {
if(arr1[i].equals(arr2[j]))
break main_loop;
}
return false;
}
main_loop:
for(int i = 0; i < arr2.length; i++) {
for(int j = 0; j < arr1.length; j++) {
if(arr2[i].equals(arr1[j]))
break main_loop;
}
return false;
}
// having got through both loops, we can now return true
}
A more advanced way: sort both arrays and walk over both of them. Time: n lg n
更高级的方法：对两个数组进行排序并遍历它们。时间：n lg n
boolean equals(String[] arr1, String[] arr2) {
if(arr1.length != arr2.length) return false;
String[] copy1 = Arrays.copyOf(arr1,arr1.length); // java.util.Arrays
String[] copy2 = Arrays.copyOf(arr2,arr2.length); // java.util.Arrays
Arrays.sort(copy1);
Arrays.sort(copy2);
for(int i = 0; i < copy1.length; i++) {
if(!copy1[i].equals(copy2[i])
return false;
}
return true;
}
An even more advanced way: use a hashmap, adding for the counts of the first string array, removing for the counts of the second string array. When you're odne all counts should be zero.
更高级的方法：使用哈希图，添加第一个字符串数组的计数，删除第二个字符串数组的计数。当您闲置时，所有计数都应为零。
boolean equal(String[] arr1, String[] arr2) {
if(arr1.length != arr2.length) return false;
Map<String, Integer> map1 = new HashMap<String,Integer>();
for(String str : arr1) {
if(!map.containsKey(str)) {
map.put(str, 1);
} else {
map.put(str, map.get(str) + 1); // add to count inthe map
}
}
for(String str : arr1) {
if(!map.containsKey(str)) {
return false; // we have an element in arr2 not in arr1 - leave now
} else {
map.put(str, map.get(str) - 1); // remove to count inthe map
}
}
for(Integer count : map.values()) {
if(count.intValue() != 0) return false;
}
return true;
}
回答by Donald Raab
If you are using Eclipse Collections, you can use a Bagto figure out if the two arrays are equal.
如果您使用的是Eclipse Collections，则可以使用 aBag来确定两个数组是否相等。
String[] s1 = {"a", "b", "c", "c"};
String[] s2 = {"c", "a", "b", "c"};
Bag<String> h1 = Bags.mutable.with(s1);
Bag<String> h2 = Bags.mutable.with(s2);
Assert.assertEquals(h1, h2);
Bags (also known as multisets) are considered equal if they have the same number of occurrences of each element. Order doesn't matter, and it properly handles duplicate elements. The advantage of using a bag backed by a hashtable is that creating one takes linear time. Sorting both takes O(n log n).
如果袋子（也称为多重集）具有相同的每个元素出现次数，则它们被认为是相等的。顺序无关紧要，它可以正确处理重复元素。使用由哈希表支持的包的优点是创建一个包需要线性时间。排序两者都需要 O(n log n)。
Note: I am a committer for Eclipse Collections
注意：我是 Eclipse Collections 的提交者
回答by Samir Mangroliya
String[] s1 = {"a","b","c"};
String[] s2 = {"b","c","a"} ;
Arrays.sort(s1);
Arrays.sort(s2);
if(Arrays.equals(s1, s2)){
System.out.println("ok");
}
回答by Denys Séguret
I suppose this is for school.
我想这是给学校的。
Possible strategies :
可能的策略：
- use Arrays.sort to sort both arrays and then use a loop to compare s1[i] to s2[i]
- use a loop and for each item of s1 look at the items of s2 to find if it contains the same
- put items of s1 into a hashset and then use a loop on s2 and look if your items are in s1
- 使用 Arrays.sort 对两个数组进行排序，然后使用循环将 s1[i] 与 s2[i] 进行比较
- 使用循环并对 s1 的每个项目查看 s2 的项目以查找它是否包含相同
- 将 s1 的项目放入散列集，然后在 s2 上使用循环并查看您的项目是否在 s1 中
回答by vonWippersnap
Set::equals
Set::equals
NB: This is a simple non-intrusive solution, but it only works if you are sure there are no duplicate entries in either of the input arrays/lists (or you want to ignore duplicates).
注意：这是一个简单的非侵入式解决方案，但它仅在您确定任一输入数组/列表中没有重复条目（或者您想忽略重复项）时才有效。
You don't need any external libraries for this one. Set<>already has an equalsmethod that does order-independent comparison.
您不需要任何外部库。 Set<>已经有一种equals方法可以进行与顺序无关的比较。
public static <T> boolean areArraysEquivalent(T[] ary1, T[] ary2) {
if (ary1 == null) {
return ary2 == null;
}
if (ary2 == null) {
return false;
}
List<T> list1 = Arrays.asList(ary1);
List<T> list2 = Arrays.asList(ary2);
return areListsEquivalent(list1, list2);
}
public static <T> boolean areListsEquivalent(List<T> list1, List<T> list2) {
if (list1 == null) {
return list2 == null;
}
if (list2 == null) {
return false;
}
Set<T> set1 = new HashSet<>(list1);
Set<T> set2 = new HashSet<>(list2);
return set1.equals(set2);
}
回答by Paul Boddington
For small arrays, I would use Arrays.sortand Arrays.equalsas others have suggested. For larger arrays you can use the following solution which has better time complexity - O(n)rather than O(n log n).
对于小型阵列，我会使用Arrays.sort和Arrays.equals其他人建议的那样。对于更大的数组，您可以使用以下具有更好时间复杂度的解决方案 -O(n)而不是O(n log n).
public static boolean haveSameElements(Object[] arr1, Object[] arr2) {
return arr1.length == arr2.length && counts(arr1).equals(counts(arr2));
}
// Map.merge and method references require Java 8
private static <T> Map<T, Integer> counts(T[] arr) {
Map<T, Integer> map = new HashMap<>();
for (T t : arr)
map.merge(t, 1, Integer::sum);
return map;
}
回答by supercat
If one will frequently be wanting to compare arrays against each other without modifying their contents, it may be helpful to define a type which encapsulates an immutable array, a sorted version thereof, a longsequence count which is guaranteed unique and at least mostly correlates with object age, and an initially-null reference to another older object which is known to match. It may also be helpful to cache a hash value which combines the hash values of all array elements.
如果人们经常想要在不修改其内容的情况下相互比较数组，那么定义一种封装不可变数组的类型、其排序版本、long保证唯一且至少主要与对象相关的序列计数可能会有所帮助年龄，以及对另一个已知匹配的旧对象的初始空引用。缓存一个组合了所有数组元素的哈希值的哈希值也可能会有所帮助。
Using such an approach, sorting would be required the first time an objects is compared to something (anything) else, but not after that. Further, if objects X and Y are both found equal to Z, then comparison between X and Y could report them as equal without having to actually examine the array contents (if Z is older than X and Y, then both will report themselves as equal to the same older object; if X is the youngest and Y the oldest, X will know it's equal to Z and Z will know it's equal to Y. When X is next compared to something, it will find out that the oldest thing it's known to be equal to is Y, so it of course would be equal to Y.
使用这种方法，第一次将对象与其他事物（任何事物）进行比较时需要进行排序，但之后则不需要。此外，如果发现对象 X 和 Y 都等于 Z，则 X 和 Y 之间的比较可以将它们报告为相等，而无需实际检查数组内容（如果 Z 比 X 和 Y 更旧，则两者都将报告自己相等到同一个较老的对象；如果 X 是最年轻的，Y 是最老的，X 会知道它等于 Z，Z 会知道它等于 Y。当 X 下一次与某物进行比较时，它会发现它所知道的最旧的东西等于是Y，所以它当然等于Y。
Such an approach would yield equality-comparison performance benefits similar to interning, but without the need for an interning dictionary.
这种方法将产生类似于实习的平等比较性能优势，但不需要实习字典。
回答by wattostudios
I'd sort the 2 arrays first, then compare line-by-line...
我会先对 2 个数组进行排序，然后逐行比较...
public boolean areArraysEqual (String[] array1,String[] array2){
if (s1.length != s2.length){
return false;
}
java.util.Arrays.sort(s1);
java.util.Arrays.sort(s2);
for (int i=0;i<s1.length;i++){
if (! s1[i].equals(s2[i])){
return false;
}
}
return true;
}
