验证二维数组是否有两个相等行的算法

Question

定义一个方法，可以判断给定的二维数组是否至少有两行完全相同。

我尝试设计了一个算法来实现这个功能，但是并没有走得很远。以下是我的尝试：

public static boolean righeUguali(int[][] a){
    boolean rUguali=false;

    for(int i=0; i<a.length; i++)
        for(int j=0; i<a[i].length; j++)
            if(Arrays.equals(a[i],a[j]))
                rUguali = true;
    return rUguali;

你能帮我修复这段代码吗？

- Daniele

---

你想用那个算法做什么？你对那段代码有什么问题？ - Youcef LAIDANI

它不起作用。显然有些问题，但我无法弄清楚是什么问题。如果两行相同，它应该返回true。 - Daniele

可能是重复问题，类似于Java数组，查找重复项。 - 4castle

你尝试过使用调试器或者输出调试信息来找到问题吗？ - MrSmith42

你在第二个for循环中使用了i<a[i].length。这不应该是j吗？ - xro7

你还需要将j=0改为j=i+1；否则你会将数组与它们自身进行比较。 - Andy Turner

Answer 1

• 您需要确保不将行与自身进行比较。为此，您需要从i+1开始设置j
• 两个循环都需要遍历行
• 这两行中首先出现的那一行不能是最后一个，否则就没有第二行可以进行比较了。
• 优化：一旦找到两行相等的情况，就可以立即停止。

以下是修改后的代码：

public static boolean righeUguali(int[][] a){
    for(int i=0; i<a.length-1; i++)
        for(int j=i+1; i<a.length; j++)
            if(Arrays.equals(a[i],a[j]))
                return true;
    return false;
}

- MrSmith42

---

特别感谢您的优化工作，非常感谢。 - Daniele

@Daniele：它仍然是**O(n²)。如果速度是一个问题：您可以通过使用HashSet来获得O(n)**。 - MrSmith42

这对于像这样的小方法来说不是问题。但我仍然喜欢发现改进代码的新方法。 - Daniele

Answer 2

这是我会的做法：

int[][] array = { { 1, 2, 3, 4, 5, 6 },
            { 7, 6, 8, 3 }, 
            { 1, 2, 3, 4 },
            { 1, 2, 3, 9, 5, 6, 32, 3125423 },
            { 8, 3 }, 
            { 1, 2, 3, 4, 5, 6 } };//same as first row
    external: for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (Arrays.equals(array[i], array[j])) {
                System.out.println("Row: " + i + " is the same as row: " + j+" (warning! 0 oriented!)" );
                break external;
            }
        }
    }

如您所见，array[] 是相当随机的，但第一行（第 0 行）与最后一行（第 5 行）是相同的，因此我会循环遍历数组一次，并在每次循环中遍历剩余的行。然后，我会比较这些数组以检查它们是否相同。如您所见，代码会打印出一条消息，然后终止（停止外部循环）。

这基于一个简单的排序算法。

编辑 #1：正如 @4castle 在评论中指出的那样，在方法上下文中，break 语句不是必需的，可以用 return 代替。

- fill͡pant͡

---

由于这是在一个方法中，您可以使用 return 来终止循环，而不是打破命名循环。 - 4castle

@4castle 的确如此，但我并没有真正针对一个方法进行编写，因为这段代码实际上是从我的一个项目中提取出来的。无论如何，我会在我的帖子中提到这一点 :) 谢谢！ - fill͡pant͡

非常感谢！它解决了我的问题。 - Daniele

@Daniele 我很高兴能帮忙！:-) - fill͡pant͡

Answer 3

通过应用近似重复问题的最简答案：

public static boolean righeUguali(int[][] a) {
    for(int i = 0; i < a.length; i++)
        for(int j = i + 1; j < a.length; j++)
            if(Arrays.equals(a[i], a[j]))
                return true;
    return false;
}

您的算法出现问题，因为j似乎是用来迭代嵌套数组的。这不是必要的，因为Arrays.equals将迭代嵌套数组。相反，将其用作第二个迭代器，以查找是否有任何其他元素与由i指定的当前元素匹配。

如果您希望获得更好的性能，则可以在重复问题上找到更快的解决方案。

- 4castle

Answer 4

没有人提到一个更快的方法是对顶层数组进行排序，然后查找两个相邻的行是否相同。如果数组是m*n，则这将需要O（mn log n）的时间，而所有现有的解决方案都需要O（mn ^ 2）的时间。

当然，如果您无法重新排序行，则首先需要复制数组 - 但是除非您的数组占用> 50％的可用RAM，否则创建副本，然后对其行进行排序仍将比现有的解决方案快得多。

- j_random_hacker

---

不客气 :) 排序是计算机科学中那些意想不到地有用的东西之一！ - j_random_hacker