唯一标识一组数字，其顺序无关紧要

Question

假设我有这 3 个整数数组：

int[] a = {1, 2, 3};
int[] b = {3, 4, 5};
int[] c = (2, 1, 3};

我正在寻找最有效的代码，将 a 视为与 c 相同（因为它们包含相同的数字但顺序不同），但考虑 a 不同于 b，b 不同于 c。

我知道我可以对它们进行排序，使 c 变为 {1, 2, 3}，因此与 a 相同，但我正在比较数百个数组，每个数组都超过三个数字，我不想我的程序对它们中的每一个进行排序，我认为一定有更好的方法。

另外，以求和为例，是行不通的，因为{1, 4, 5}中的数字之和与{1, 3, 6}中的数字之和相同。

而且乘积也不行，因为 {1, 2, 6} 中数字的乘积与 {1, 3, 4} 中数字的乘积相同。

Answer 1

排序是一个 O(nlog(n)) 操作（在最坏的情况下）。相反，您可以通过运行在两个数组上获得 O(n) 解决方案，只计算其中的元素:

public static boolean hasSameElements(int[] a, int[] b) {
    return countElements(a).equals(countElements(b);)
}

private static Map<Integer, Long> countElements(int[] arr) {
    return Arrays.stream(arr)
                 .boxed()
                 .collect(Collectors.groupingBy(Function.identity(), 
                          Collectors.counting()));
}

编辑：
虽然它不会改变算法的大 O 表示法，但稍微不那么优雅的解决方案可以通过快速失败来更好地处理不匹配的数组：

public static boolean hasSameElements(int[] a, int[] b) {
    if (a.length != b.length) {
        return false;
    }

    Map<Integer, Long> popCount =
            Arrays.stream(a)
                  .mapToObj(Integer::valueOf)
                  .collect(Collectors.groupingBy(Function.identity(), 
                           Collectors.counting()));

    for (int elem : b) {
        Long count = popCount.get(elem);
        if (count == null) {
            return false;
        }
        count--;
        if (count == 0L) {
            popCount.remove(elem);
        } else {
            popCount.put(elem, count);
        }
    }

    return popCount.isEmpty();
}

Answer 2

将数组中的所有数字缩减为一个数字进行比较的想法是正确的。这种方法称为哈希。一个好的属性散列是尽可能避免将多组输入映射到同一个输出。加法和乘法是非常差的散列函数，并且有大量关于好的散列函数的文献。在 java 中，您可以使用 Arrays.hashCode(int[]) 函数对数组进行良好的哈希处理。

当然，尽管这种散列具有良好的质量，但不能保证两个数组不会产生相同的值。因此，这是实现比较功能的方法：

boolean equals(int[] a, int[]b) {
  if (a.length != b.length)
    return false;
  if (a == b)
    return true;
  if (Arrays.hashCode(a) != Arrays.hashCode(b)) 
    return false;
  for(int i=0; i< a.length; i++) {
    if (a[i] != b[i])
      return false;
  return true;
}

注意，只有当两个参数不指向同一个数组时才执行逐元素比较，并且散列相同。

编辑：有人向我指出，Arrays.hashCode 可能会对具有不同顺序的相同值的数组产生不同的结果，这是真的，事实上我忽略了顺序。在平均情况下，首先对数组进行排序是 O(MNlogN)（M 是数组的数量，N 是平均长度）。但是，如果数组中的重复次数很少，则平均复杂度更接近于 O(MN)，因为只有具有相同长度和哈希码的数组才需要排序，这是不太可能的。

boolean equals(int[] a, int[]b) {
  if (a.length != b.length)
    return false;
  if (a == b)
    return true;
  if (hashCode(a) != hashCode(b)) 
    return false;
  Arrays.sort(a);
  Arrays.sort(b);
  for(int i=0; i< a.length; i++) {
    if (a[i] != b[i])
      return false;
  return true;
}

private int hashCode(int[] a) {
  int res = 0;
  for(int i=0; i<a.length; i++) {
    res ^= a[i]
  }
  return res;
}

Answer 3

我假设数组没有任何内部重复项，例如 {1, 2, 2, 4}。首先检查长度是否相同。如果它们的长度相同，则从第一个数组创建一个 Set。将第二个数组 A2 中的元素一次一个地添加到集合中。添加 A2 中的每个元素时，检查它是否已添加且未作为重复项被拒绝。如果 A2 中的任何元素不重复，则这两个数组不相同。如果 A2 中的所有元素都被拒绝为重复项，则这两个数组的大小和内容相同，但顺序不一定相同。

唯一标识一组数字，其顺序无关紧要

Uniquely identify an array of numbers whose order doesn't matter

java

arrays

processing-efficiency