Javaが配列がラテンの正方形かどうかを調べるメソッド

Question

配列がLatin Squaresかどうかを調べる、入力が2次元配列intのメソッドでプログラムを作成しています。

例えばラテン方陣は次のようになります。

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

あなたが最小の正方形の許可のための簡単なテストを書き、** TDD **方法でそれを行うために必要な出力

true 
true 
true 
true 
false 
false 
false