检查数组是否为拉丁方的 Java 方法

Question

我正在创建一个程序，其方法的输入是一个 2D int 数组，该方法检查数组是否为 Latin Squares .

例如，拉丁方看起来像这样:

1 2 3
2 3 1
3 1 2

这是我到目前为止的代码:

public class LatinSquare {

  public boolean isLatinSquare(int[][] a){

    int[] row= new  int[a.length];
    int[] column = new int[a[0].length];

    for (int j = 0; j<column.length; j++){
      for (int i = 0; i<row.length;i++){
        row[i] = a[i][j];
      }

      for (int i = 0; i<row.length -1; i++){
        for (int x= i+1; x<=row.length;x++){
          if (row[i]==row[x]) 
            return false;
        }
      }
   }
}

代码并不完全完整，但我只是想知道如果我做错了什么，在我走向错误的方向之前是否有人可以回答一些问题。我的问题:这是检查数组以查看它们是否满足拉丁方的最佳方法吗？我的思维过程是从“0”列开始，然后遍历该行，将每个数字相互比较，确保它们不相等，然后以这种方式遍历每一列。这是处理这个问题的错误方法吗？

Answer 1

大量嵌套循环会降低性能。这是一个更快的版本，但它使用更多的内存。

它依赖于 1 到 N 范围内的正方形值，其中 N 是正方形大小。

private static boolean isLatinSquare(int[][] square) {
    boolean[][] foundInRow = new boolean[square.length][square.length];
    boolean[][] foundInCol = new boolean[square.length][square.length];
    for (int row = 0; row < square.length; row++) {
        if (square[row].length != square.length)
            return false; // Not a square
        for (int col = 0; col < square.length; col++) {
            int idx = square[row][col] - 1;
            if (foundInRow[row][idx] || foundInCol[col][idx])
                return false;
            foundInRow[row][idx] = foundInCol[col][idx] = true;
        }
    }
    return true;
}

测试

System.out.println(isLatinSquare(new int[][] { {1, 2, 3},
                                               {2, 3, 1},
                                               {3, 1, 2} }));
System.out.println(isLatinSquare(new int[][] { {1, 2, 3},
                                               {3, 1, 2},
                                               {2, 3, 1} }));
System.out.println(isLatinSquare(new int[][] { {1, 3, 2},
                                               {2, 1, 3},
                                               {3, 2, 1} }));
System.out.println(isLatinSquare(new int[][] { {1, 3, 2},
                                               {3, 2, 1},
                                               {2, 1, 3} }));
System.out.println(isLatinSquare(new int[][] { {1, 3, 2},
                                               {3, 2, 1},
                                               {1, 3, 2} }));
System.out.println(isLatinSquare(new int[][] { {1, 3, 1},
                                               {3, 2, 3},
                                               {2, 1, 2} }));
System.out.println(isLatinSquare(new int[][] { {1, 2, 3},
                                               {2, 3},
                                               {3, 1, 2} }));

输出

true
true
true
true
false
false
false