java - Java：检查数组的相等性（顺序无关紧要）

Question

我有两个String数组，比方说：

String[] s1 = {"a","b","c"}
String[] s2 = {"c","a","b"} 

//这些数组应该相等

我想以“最干净”的方式检查它们的平等性。

我尝试使用Arrays.equals(s1,s2)但我得到一个错误的答案。我想这种方法关心元素的顺序，我不希望这很重要。

你能告诉我如何以一种好的方式做到这一点吗？

Answer 1

• Arrays.sort(s1);
• Arrays.sort(s2);
• Arrays.equals(s1,s2);

如果您不想修改原始数组

 Arrays.equals( Arrays.sort( Arrays.copyof(s1,s1.length)),
                Arrays.sort( Arrays.copyof(s2,s2.length)) );

Arrays.sort() 使用优化的快速排序，平均为 nlog(n)，但在最坏的情况下为 O(n2)。来自 java 文档。所以最坏的情况是 O(n2)，但实际上大多数情况下是 O(nlogn)。

排序算法是经过调整的快速排序，改编自 Jon L. Bentley 和 M. Douglas McIlroy 的“Engineering a Sort Function”，Software-Practice and Experience，Vol。23(11) P. 1249-1265（1993 年 11 月）。该算法在许多数据集上提供 n*log(n) 性能，导致其他快速排序降低到二次性能。

Answer 2

其他人建议对数组进行排序。但是由于您正在寻找“最干净”的解决方案，我认为不应触及原始数组。因此：

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

Answer 3

如果您使用的是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);

如果袋子（也称为多重集）每个元素的出现次数相同，则认为它们是相等的。顺序无关紧要，它可以正确处理重复元素。使用由哈希表支持的包的优点是创建一个包需要线性时间。对两者进行排序都需要 O(n log n)。

注意：我是 Eclipse Collections 的提交者

Answer 4

人道方式：

遍历第一个数组，检查第二个数组中的每个元素是否存在，然后对第一个数组上的第二个数组执行相同的操作。时间：n^2。请注意，此方法假定没有元素重复。如果是这样，您将不得不，对于您要检查的每个元素，回到开头并计算该元素有多少个实例（例如 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
}

一种更高级的方法：对两个数组进行排序并遍历它们。时间：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;
}

一种更高级的方法：使用 hashmap，添加第一个字符串数组的计数，删除第二个字符串数组的计数。当你很高兴时，所有计数都应该为零。

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

Answer 5

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

Answer 6

Set::equals

注意：这是一个简单的非侵入式解决方案，但只有在您确定输入数组/列表中没有重复条目（或者您想忽略重复项）时才有效。

您不需要任何外部库。 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);
}

Answer 7

我会先对 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;
}

Answer 8

我想这是给学校的。

可能的策略：

• 使用 Arrays.sort 对两个数组进行排序，然后使用循环将 s1[i] 与 s2[i] 进行比较
• 使用循环，并为 s1 的每个项目查看 s2 的项目以查找它是否包含相同的
• 将 s1 的项目放入哈希集中，然后在 s2 上使用循环并查看您的项目是否在 s1

Answer 9

如果人们经常想要在不修改其内容的情况下将数组相互比较，那么定义一种封装不可变数组的类型、其排序版本、long保证唯一且至少大部分与对象相关的序列计数可能会有所帮助年龄，以及对另一个已知匹配的旧对象的初始空引用。缓存一个组合了所有数组元素的哈希值的哈希值也可能会有所帮助。

使用这种方法，第一次将对象与其他东西（任何东西）进行比较时需要进行排序，但在那之后就不需要了。此外，如果发现对象 X 和 Y 都等于 Z，则 X 和 Y 之间的比较可以报告它们相等，而不必实际检查数组内容（如果 Z 比 X 和 Y 旧，则两者都将报告自己相等到同一个较老的对象；如果 X 是最年轻的，Y 是最老的，X 会知道它等于 Z，Z 会知道它等于 Y。当 X 下次与某物进行比较时，它会发现它已知的最旧的东西等于是Y，所以它当然等于Y。

这种方法将产生类似于实习的平等比较性能优势，但不需要实习字典。

Answer 10

对于小型阵列，我会使用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;
}