判断一个n*n矩阵是不是拉丁方~

Question

判断一个n*n矩阵是不是拉丁方~
复杂度好点的算法

Answer 1

百度的：用从1开始的n个连续正整数排成n行n列的方阵，如果每一行和每一列都没有重复的数，就称为一个n阶拉丁方。因为这样的方阵最早填充的是拉丁字母，故名。

Answer 2

可以考虑用Arrays类来做，一行一个数组。然后提取每列的对应元素新建列数组。做比较

Answer 3

n 比较小的时候可以用位运算
n 较大的就用数组判重public class Test { public static void main(String[] args) { int[][] matrix = {{1,2,3,4,5,6,7,8,9},{2,3,4,5,6,7,8,9,1},{3,4,5,6,7,8,9,1,2},
{4,5,6,7,8,9,1,2,3},{5,6,7,8,9,1,2,3,4},{6,7,8,9,1,2,3,4,5},
{7,8,9,1,2,3,4,5,6},{8,9,1,2,3,4,5,6,7},{9,1,2,3,4,5,6,7,8},
};
System.out.println(isLadinMatrix(matrix));
}

    public static boolean isLadinMatrix(int[][] matrix){
     int result = 0;
     for (int i = 0; i < matrix.length; i++) {
     result |= 1 << i;
if(matrix[i].length != matrix.length) 
return false;
}
     if(matrix.length > 64)
     return isLadinMatrix02(matrix);
     long[] temp = new long[2 * matrix.length];
     for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
temp[i] ^= 1 << (matrix[i][j] - 1);
temp[j + matrix.length] ^= 1 << (matrix[i][j] - 1);
}
}
     for (int i = 0; i < temp.length; i++) {
if((temp[i] & result) != result) return false;
}
     return true;
    }    private static boolean isLadinMatrix02(int[][] matrix){
     //未完成
     //仿 isLadinMatrix 改写，上边是用位运算，这里是用数组代替
     boolean[][] temp = new boolean[2 * matrix.length][matrix.length];
     return false;
    }
}

Answer 4

老套路
要提高速度最容易想到的是hash/bitmap/空间换时间
这里采用后面两种
用java.util.BitSet简单实现下就行
用来判断循环到某位置的时候，
这个位置对应的行，列是否有和它值一样的情况，
有了直接返回false
时间复杂度初步估计为O(n^2)
public static boolean test(int[][]a) {
//异常条件判断
if(a == null ) return false;
int length = a.length;
for(int i=0;i<a.length;i++) {
if(a[i] == null || a[i].length != length) {
return false;
}
}
//
System.out.println("gg");
BitSet []b1 = new BitSet[length];
for(int i=0;i<length;i++) {
//初始均为false
b1[i] = new BitSet(length+1);
}
BitSet []b2 = new BitSet[length];
for(int i=0;i<length;i++) {
//初始均为false
b2[i] = new BitSet(length+1);
}
for(int i=0;i<length;i++) {
for(int j=0;j<length;j++) {
if(b1[a[i][j]-1].get(i)) {
return false;
}else {
b1[a[i][j]-1].set(i, true);
}
if(b2[a[i][j]-1].get(j)) {
return false;
}else {
b2[a[i][j]-1].set(j, true);
}
}
}
return true;
}

Answer 5

异常情况还是有很多的
仅供test之用
嘿嘿
例如9*9的矩阵
里面有个值为非1-9的值