程序员人生网站导航

剑指offer 面试题20―顺时针打印矩阵

栏目：php教程时间：2015-05-11 09:21:54

题目：

输入1个矩阵，依照从外向里以顺时针的顺序顺次打印出每个数字。
例如：如果输入以下矩阵：

1             2             3             4
5             6             7             8
9             10            11             12
13            14            15             16
则顺次打印出数字1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6,7, 11, 10。

基本思想：

通常当我们遇到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 rows, 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,2,3,4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}; PrintMatrixClockWisely(nMatrix, 4, 4); cout << endl; return 0; }

------分隔线----------------------------

上一篇 生成所有的BST

下一篇 如何快速高效的接入移动第三方SDK

------分隔线----------------------------