打印环形数字矩阵,顺时针,边计算边打印,时间复杂度O(n^2)

时间:2021-08-13 17:10:53

一个面试题,自己写的,跟网上大部分现有的不太一样,直接计算出(i,j)的值打印。

nBegin是指定的矩阵的第一个元素。
nLengthSide是指定的矩阵的长宽。
nLoop是第几环。
nLengthSideLoop是第nLoop环的长宽。
nBase是第nLoop环的第一个元素,这个值的推导过程用到了高中的等差数列,结果是前n项和,注意数学里的2*(1/2)=1,代码中=0。
将环的边分为四组:
上边组:从左到右,递增
右边组:从上到下,递增
左边组:从上到下,递减
下边组:从左到右,递减
针对每组找到通项公式直接printf出来。

printf处4行代码可以进行合并,为直观未进行处理。

打印环形数字矩阵,顺时针,边计算边打印,时间复杂度O(n^2)

BOOL
PrintLoopFormMatrix(
__in int nBegin,
__in int nLengthSide
)
{
BOOL bRet = FALSE;

int i = 0;
int j = 0;
int nLoop = 0;
int nLengthSideLoop = 0;
intnBase= 0;


__try
{
for (; i < nLengthSide; i ++)
{
for (j = 0; j < nLengthSide; j++)
{
if (i <= j)
{
if (i <= nLengthSide - 1 - j)
{
// 上
nLoop = i + 1;
nBase = nBegin + (nLoop - 1) * (4 * nLengthSide - 4 * (nLoop - 1));
nLengthSideLoop = nLengthSide - 2 * nLoop + 2;
printf("%d\t", nBase + 0 * (nLengthSideLoop - 1) + j - (nLoop - 1));
}
else
{
// 右
nLoop = nLengthSide - j;
nBase = nBegin + (nLoop - 1) * (4 * nLengthSide - 4 * (nLoop - 1));
nLengthSideLoop = nLengthSide - 2 * nLoop + 2;
printf("%d\t", nBase + 1 * (nLengthSideLoop - 1) + i - (nLoop - 1));
}
}
else
{
if (i <= nLengthSide - 1 - j)
{
// 左
nLoop = j + 1;
nBase = nBegin + (nLoop - 1) * (4 * nLengthSide - 4 * (nLoop - 1));
nLengthSideLoop = nLengthSide - 2 * nLoop + 2;
printf("%d\t", nBase + 4 * (nLengthSideLoop - 1) - 1 - (i - (nLoop - 1) - 1));
}
else
{
// 下
nLoop = nLengthSide - i;
nBase = nBegin + (nLoop - 1) * (4 * nLengthSide - 4 * (nLoop - 1));
nLengthSideLoop = nLengthSide - 2 * nLoop + 2;
printf("%d\t", nBase + 3 * (nLengthSideLoop - 1) - 1 - (j - (nLoop - 1) - 1));
}
}
}

printf ("\n");
}

bRet = TRUE;
}
__finally
{
;
}

return bRet;
}