在三个二维数组中查找相似的行

Question

在三个二维数组中查找相似的行

3

什么是在Java中解决以下问题的最佳方法? 有三个二维数组，它们具有相等的行数和列数：

Array1:
[1]: {1, 2, 3}
[2]: {2, 2, 4}
[3]: {1, 1, 1}

Array2:
[1]: {1, 2, 0}
[2]: {1, 2, 3}
[3]: {1, 0, 1}

Array3:
[1]: {1, 1, 1}
[2]: {1, 2, 3}
[3]: {1, 0, 1}

我需要查找所有数组中都存在的行索引。在上面的示例中，答案应该是：[1],[2],[2]

数组1 [1]: {1, 2, 3}

数组2： [2]: {1, 2, 3}

数组3： [2]: {1, 2, 3}

更新：有没有内置函数可以实现这个功能？还是说只有使用FOR循环才是唯一的解决方案？

- Klausos Klausos

6个回答

1

据我所知，这方面没有内置函数。

您需要编写自己的函数来实现它（使用for循环）。

如果它不能正常工作或需要优化，请发布一些代码以展示您尝试了什么。

- Azodious

1

我会按照以下步骤进行：

创建一个类，该类接受数组中的一行并实现hashcode和equals方法。
将每一行（包装在上述类中）插入到两个HashMaps中的前两个数组中。
对于最后一个数组中的每一行，确定它们是否存在于HashMaps中。

编辑#2，意识到映射需要反转。

private Map<MyClass, Integer> map(int[] array){
  Map<MyClass, Integer> arrayMap = new HashMap<>();
  for (int i; i<array.length; i++)
        arrayMap.put(new MyClass(array[i]), i);
}

private mySearch(){
   int[] array1, array2, array3;

   Map<MyClass, Integer> map1 = map(array1);
   Map<MyClass, Integer> map2 = map(array2);

   for (int i=0; i<array3.lenght; i++){
      MyClass row = new MyClass(array3[i]);
      Integer array1Row = map1.get(row);
      Integer array2Row = map2.get(row);

      if (array1Row != null && array2Row != null){
         // Matching rows found
      }
   }
}

- John B

请您能否举个第二步的例子？ - Klausos Klausos

1

请检查这段代码：

ArrayList<Integer[]> arr1 = new ArrayList<Integer[]>();
    arr1.add(new Integer[]{1,2,3});
    arr1.add(new Integer[]{2,2,5});
    arr1.add(new Integer[]{1,1,1});

    ArrayList<Integer[]> arr2 = new ArrayList<Integer[]>();
    arr2.add(new Integer[]{1,2,0});
    arr2.add(new Integer[]{1,2,3});
    arr2.add(new Integer[]{1,0,1});

    ArrayList<Integer[]> arr3 = new ArrayList<Integer[]>();
    arr3.add(new Integer[]{1,1,1});
    arr3.add(new Integer[]{1,2,3});
    arr3.add(new Integer[]{1,0,1});


    for (int r = 0 ; r < arr1.length() ; r++) {
        for(int s = 0 ; s < arr2.length() ; s++){
            for(int t = 0 ; t < arr3.length() ; t++){
                if(Arrays.deepEquals(arr1.get(r), arr2.get(s))){

                }else
                {
                    continue;
                }
                if(Arrays.deepEquals(arr1.get(r), arr3.get(t))){
                    System.out.println(r + " " + s + " " +t);;  
                }
            }

        }
    }

- Kushan

如果每个数组的行数不同，它还能正常工作吗？ - Klausos Klausos

此外，如果数组的数量大于3，它还能工作吗？ - Klausos Klausos

它可以适用于数组中的任意行数，只需更新循环索引即可。然而，这是可能的最低效解决方案O(n^3)。Mike的解决方案至少比这个更有效率。我认为哈希解决方案甚至更好。 - John B

0

编写一个方法，接受两个参数：要搜索的二维数组和一个一维数组行。如果没有找到匹配项，则该方法返回-1，否则返回匹配行的索引。
对于第一个数组的每一行： 2a. 调用该方法，传递第一个数组中的行和Array2。 2b. 如果2a返回>0，则调用该方法，传递相同的行和Array3
如果2b返回>0，则输出返回的索引。

- Manish

1

两个问题：第一个应该是 >=0。第二，这是低效的，至少是 O(n^2)，如果不是更接近 O(n^3)。如果数组1中的每一行都存在于数组3中，那么这将是 O(n^3)。在我看来，哈希是一个更好的选择。 - John B

-1

请查看Arrays.deepEquals()方法。它将检查两个数组是否相等。

- narek.gevorgyan

这是一种确定匹配的好方法，但算法的时间复杂度将会是O(n^2)。 - John B

不行，因为不能保证行的顺序相同。一个数组中的第一行可能与另一个数组中的第二行匹配，但 deepEquals() 不会将其视为匹配。 - Mike Nakis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mike Nakis · Accepted Answer

首先，编写一个名为AreRowsEqual()的函数，用于比较两行。因此，现在问题已经被重新阐述为在3个数组中查找相似元素。

其次，尝试考虑一种解决方案，该方案基于您之前的知识最接近的内容：要在两个数组中查找相等的元素，您需要使用双重嵌套循环。因此，要在三个数组中查找相等的元素，您需要使用三重嵌套循环，对吧？

好的，现在，请将其标记为不好的、不好的、不好的解决方案，因为它的时间复杂度是O(n^3)。我们应该能够做得更好。

考虑这个问题：为了使一个元素在三个数组中相似，首先它必须在前两个数组中相似；然后，在接下来的两个数组中也必须相似。这种算法的复杂度将类似于O(x*n)，其中x是数组的数量。这样好多了，对吧？（我无法确定O()的确切值，有人能帮忙吗？）编辑：结果证明它是O((n^2)*(x-1))，当n > x时比O(n^3)好得多。--结束编辑 顺便说一句，这让你可以忘记严格要求只有3个数组，而只需考虑一些x个数组。

我写了一种方法，得到了一个赞，然后我意识到它行不通，所以我删除了它。这是另一次尝试，我相信这会起作用。

创建一个二维整数数组。我们将称之为“矩阵”。该矩阵将具有x列，行数将是第一个数组的行数。（是的，即使您的数组长度不同，这也可以工作。）此矩阵单元格中的数字将匹配行索引。因此，例如，在我描述的算法完成后，矩阵中的{1,3,2}行将告诉我们第一个数组的第1行与第二个数组的第3行和第三个数组的第2行相匹配。我们将使用-1表示“无匹配项”。

因此，矩阵的第一列需要用第一个数组的所有行的索引进行初始化，即数字0、1、2、...n，其中n是第一个数组中的元素数量。

对于每个额外的数组，请按以下方式填充矩阵中的列：循环遍历矩阵中当前列的每一行，并计算单元格，如下所示：如果前一列的相应单元格为-1，则将-1传递到此单元格。否则，在当前数组中查找与前一个数组的相应行匹配的行，如果找到，则将其索引存储在此单元格中。否则，在此单元格中存储-1。

重复执行所有数组，即矩阵中的所有列。最终，您的匹配行是那些在矩阵的最后一列中没有-1的行。

如果您真的关心效率，可以像John B建议的那样编写一个不可变类Row，该类封装（包含对）一行并实现hashCode()和equals()。equals()可以使用Arrays.deepEquals()实现。在Arrays中可能还有一些好东西叫做deepHashCode()，否则您将需要自己编写。