如何检查两个简单的二维数组是否具有相同的一维数组？ （顺序和重复无关紧要）

Question

我的主要 objective 是 return 如果二维数组 int[ ][ ] 的所有元素 int[ ][ ] 都存在于另一个二维数组中。

我已经尝试使用 Arrays.deepEquals() 但在这种情况下，元素的顺序很重要，这不是目的。

• Int[ ][ ] 数组不会超过 15，例如。
• Int[ ][ ] 数组的长度始终相同。
• Int[ ][ ] 数组顺序无关紧要，但 Int[ ] 数组顺序重要。
• Int[ ] 数组总是一对。

预期：

int[][] array1 = {{1, 2}, {2, 2}, {0, 1}, {3,4}} // Main Array

int[][] array2 = {{0, 1}, {2, 2}, {3,4} {1, 2}}} // Expected: true

int[][] array3 = {{6, 3}, {1, 2}, {7,4} {0, 1}}} // Expected: false
  

这是我的solution/try:

// Check if an int[] array (element) belongs to an int[][] array.

public static boolean inVector(int[][] 2dArray, int[] 1dArray) {

    for (int i = 0; i < 2dArray.length; i++) {
        for (int j = 0; j < 2dArray[i].length; j++) {

            if (1dArray[0] == 2dArray[i][0] && 1dArray[1] == 2dArray[i][1]) {
                return true;
            }
        }
    }

    return false;
}


// Check if all int[] arrays of an int[][] belong to another int[][] array.

// This is not working properly

public boolean allBelongs() {

  boolean belongs = false;

  for (int i = 0; i < array1.length; i++) {
     
     if (inVector(array1, array2()[i])) {
        belongs = true;
     }
     
     else {
        belongs = false;
     }
  }

    return belongs;
}

编辑： 我解决了颠倒解决方案逻辑的问题。发布了自己的答案。

Answer 1

此解决方案应该有效。如果数组相对较小（例如 2 x 4），它可能比其他解决方案更快：

import java.util.Arrays;

class Main {
  public static boolean isSubarrayUnordered(int[][] child, int[][] parent) {
    for (int[] childSubarray : child) {
      boolean found = false;
      for (int[] parentSubarray : parent) {
        if (Arrays.equals(childSubarray, parentSubarray)) {
          found = true;
          break;
        }
      }
      if (!found) return false;
    }
    return true;
  }

  public static void main(String[] args) {
    int[][] array1 = {{1, 2}, {2, 2}, {0, 1}, {3, 4}};
    int[][] array2 = {{0, 1}, {2, 2}, {3, 4}, {1, 2}};
    int[][] array3 = {{1, 2}, {2, 2}, {0, 999}, {3, 4}};

    System.out.println("array1 in array2? " + isSubarrayUnordered(array1, array2));
    System.out.println("array1 in array3? " + isSubarrayUnordered(array1, array3));
  }
}

对于中等大小的数组（可能有数百到数千个元素），创建两个数组的排序副本并在两个数组上使用两个迭代器可能会更快 itChild, itParent。对于itChild的每个元素，如果itParent的当前元素相等（使用Arrays.equals，则itChild和itParent都前进。否则，只前进itParent. 重复直到 itChild (return true) 中没有更多元素或 itParent (return false).

对于非常大的数组（数百万到数十亿个元素），创建副本的成本可能高得令人望而却步。您可能希望使用 sha256 散列之类的东西创建数组的压缩表示，然后仅比较元素的散列。如果数组非常大，则 return 得到错误答案的可能性很小。

Answer 2

您可以使用 IntBuffer，它可以包装 int[] 数组并提供反映数组内容的 equals 和 hashCode 实现。

public static boolean sameSubArrays(int[][] array1, int[][] array2) {
    if(array1 == array2) return true;
    HashSet<IntBuffer> set = new HashSet<>();
    for(int[] a: array1) set.add(IntBuffer.wrap(a));
    for(int[] a: array2) if(!set.contains(IntBuffer.wrap(a))) return false;
    return true;
}

这很简单并且在线性时间内运行，因此可以处理大型数组。它具有您的测试用例的预期结果。

int[][] array1 = {{1, 2}, {2, 2}, {0, 1}, {3,4}};
int[][] array2 = {{0, 1}, {2, 2}, {3, 4}, {1, 2}};
System.out.println(sameSubArrays(array1, array2)); // true

但它不考虑重复项。如果出现次数必须匹配具有相同内容的子数组，则必须扩展解决方案以使用映射来计算出现次数。

public static boolean sameSubArrays(int[][] array1, int[][] array2) {
    if(array1 == array2) return true;
    if(array1.length != array2.length) return false;
    HashMap<IntBuffer, Integer> map = new HashMap<>();
    for(int[] a: array1) map.merge(IntBuffer.wrap(a), 1, Integer::sum);
    for(int[] a: array2)
        if(map.merge(IntBuffer.wrap(a), -1, Integer::sum) < 0) return false;
    return true;
}

由于您的示例没有重复项，因此结果仍然相同。

Answer 3

不是验证 int[][] 中是否存在所有 int[]，而是验证一个 int[] 是否存在。

public boolean allBelongs() {

  for (int i = 0; i < array1.length; i++) {
 
    if (!inVector(array1, array2()[i])) {
       return false;
    }
  }

  return true;
}