[discussion] how to approve that the given 9*9 is a sudoku# JobHunting - 待字闺中
l*a
1 楼
前一阵子有人发的google电面题。我想了想，解法如下，请批评指正。
简化为判断每一行/一列/3*3矩阵是否是1-9的一个permutation
for(i=0;i<9;i++)
{
if((a[i]>9)||(a[i]<0)) { return false;}
}
for(i=0;i<9;i++)
{
a[a[i]-1]+=9;
}
for(i=0;i<9;i++)
{
if((a[i]>2*9+1)) //for location i+1,add 9 at least twice so that there
is duplicate elements i+1
{ return false;}
}
return true.
time complexity O(n2)
简化为判断每一行/一列/3*3矩阵是否是1-9的一个permutation
for(i=0;i<9;i++)
{
if((a[i]>9)||(a[i]<0)) { return false;}
}
for(i=0;i<9;i++)
{
a[a[i]-1]+=9;
}
for(i=0;i<9;i++)
{
if((a[i]>2*9+1)) //for location i+1,add 9 at least twice so that there
is duplicate elements i+1
{ return false;}
}
return true.
time complexity O(n2)
