当N=4时,对应的蛇形矩阵如下图:
图 1
将该蛇形矩阵中元素的坐标代替其元素值时,得到如图2的矩阵,此时横坐标i和纵坐标j的和m=i+j具有一定的规律。当m为偶数时,原矩阵(图1中矩阵)中的元素值沿左下方增大,当m为奇数时,原矩阵中的元素值沿右上方增大。
图 2
由于只能使用O(1)的空间复杂度,不能使用上篇博文中的方法。不过可以发现当m<N时,i+j<m的点数为m(m+1)/2,故i+j=m的点的值是在m(m+1)/2的基础上根据i,j值进行加值。当m>=N时,可重新将坐标原点定义为右下角(如图3),将元素值从16按图3中所指方向进行减值。
此种方法的代码如下:
void printSnakeOfN2(int N)
{
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
int m=i+j;
if(m<N)
{
if( m%2!=0 )
printf( "%d ",m*(m+1)/2+1+(m-j) );
else
printf( "%d ",m*(m+1)/2+1+(m-i) );
}
else
{
m=2*N-2-m;
if( m%2!=0 )
printf( "%d ",N*N-( m*(m+1)/2+(m-(N-1-j)) ) );
else
printf( "%d ",N*N-( m*(m+1)/2+(m-(N-1-i)) ) );
}
}
printf("\n");
}
}