剑指offer 面试题20―顺时针打印矩阵
|
题目： 输入1个矩阵，依照从外向里以顺时针的顺序顺次打印出每个数字。 1 2 3 4
基本思想： 通常当我们遇到1个复杂的问题的时候，我们可以用图形帮助我们思考。由于我们是以从外圈到内圈的顺序顺次打印，我们在矩阵中标注1圈作为我们分析的目标。在下图中，我们设矩阵的宽度为columns，而其高度为rows。我们我们选取左上角坐标为(startX,startY)，右下角坐标为(endX,endY)的1个圈来分析。
由于endX和endY可以根据startX、startY和columns、rows来求得，因此此时我们只需要引入startX和startY两个变量。我们可以想象有1个循环，在每次循环里我们从(startX,startY)动身依照顺时针打印数字。 接着我们分析这个循环结束的条件。对1个5×5的矩阵而言，最后1圈只有1个数字，对应的坐标为(2,2)。我们发现5 > 2 * 2。对1个6×6的矩阵而言，最后1圈有4个数字，对应的坐标依然为(2,2)。我们发现6 > 2 * 2仍然成立。因而我们可以得出，让循环继续的条件是columns > startX * 2 && rows > startY * 2。接下来我们分析如何依照顺时针的顺序打印1圈的数字。犹如在图中标注的那样，我们可以分4步来打印：第1步是从左到右打印1行（上图中黄色区域），第2步是从上到下打印1列（上图中绿色区域），第3步从右到左打印1行（上图中蓝色区域），最后1步是从下到上打印1列（上图中紫色区域）。也就是我们把打印1圈数字这个问题，分解成4个子问题。 值得注意的是，最后1圈可能退化成只有1行、只有1列、乃至只有1个数字，因此打印这样的1圈就不需要4步了。
#include <iostream>
using namespace std;
void PrintMatrixIncircle(int nArr[][4],int rows,int columns,int nStart)
{
int nEndX = columns - 1 -nStart;
int nEndY = rows - 1 -nStart;
//从左到右打印1行
for (int i=nStart; i<=nEndX; i++)
{
cout << nArr[nStart][i] << " ";
}
//从上到下打印1列
if (nEndY > nStart)
{
for (int j=nStart+1; j<=nEndY; j++)
{
cout << nArr[j][nEndX] << " ";
}
}
//从右到左打印1行
if (nEndY > nStart && nEndX > nStart)
{
for (int t=nEndX⑴; t>=nStart; t--)
{
cout << nArr[nEndY][t] << " ";
}
}
//从下到上打印1列
if (nEndY ⑴ > nStart && nEndX > nStart)
{
for (int n=nEndY⑴; n>=nStart+1; n--)
{
cout << nArr[n][nStart] << " ";
}
}
}
//顺时针打印矩阵，行数为rows，列数为columns
void PrintMatrixClockWisely(int nArr[][4],int columns)
{
if (nArr == NULL || rows <= 0 || columns <= 0)
return ;
int nStart = 0;
while (rows>(nStart*2) && columns>(nStart*2))
{
PrintMatrixIncircle(nArr,rows,columns,nStart);
nStart++;
}
}
int main()
{
int nMatrix[4][4] = {
{1,4},{5,8},{9,10,12},{13,16}};
PrintMatrixClockWisely(nMatrix,4);
cout << endl;
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
