2

我的主要目标是返回一个 2D 数组 int[ ][ ] 的所有元素 int[ ] 是否存在于另一个 2D 数组中。

我已经尝试过使用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

这是我的解决方案/尝试：

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

编辑：我解决了反转解决方案逻辑的问题。发表了自己的答案。

4

3 回答 3

4

您可以使用IntBufferwhich 可以包装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;
}

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

于 2022-01-07T08:17:20.813 回答
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。重复直到 (return ) 中没有更多元素或 (return ) 中没有更多itChild元素。trueitParentfalse

对于非常大的数组（数百万到数十亿个元素），创建副本的成本可能非常昂贵。您可能希望使用sha256哈希之类的东西创建数组的压缩表示，然后只比较元素的哈希值。但是，如果数组非常大，则返回错误答案的可能性很小。

于 2022-01-07T03:37:18.130 回答
0

我可以验证 ONE int[] 是否不存在，而不是验证 int[][] 中是否存在 ALL int[]。

public boolean allBelongs() {

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

  return true;
}
于 2022-01-07T15:22:46.183 回答