剑指Offer——顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

如果输入如下矩阵： 

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.

方法一

按照右、下、左、上的顺序依次打印，将已经遍历过的值标记出来，遇到边界或者已经遍历过的就换方向。

代码

class Solution { public: vector<int> printMatrix(vector<vector<int>> matrix) { row = matrix.size(); if( row == 0 ) return res; col = matrix[0].size(); if( col == 0 ) return res; visited = vector<vector<bool>>( row, vector<bool>(col,false) ); int flag = 0; while( count < row*col ) { switch(flag) { case 0:{rth++;cth++;break;}//right case 1:{cth--;rth++;break;}//down case 2:{rth--;cth--;break;}//left case 3:{cth++;rth--;break;}//up } move( matrix, flag ); flag++; if( flag == 4 ) flag = 0; } return res; } vector<int> res; int row,col; int count = 0; int rth = -1; int cth = -1; vector<vector<bool>> visited; void move( vector<vector<int>> matrix, int flag ) { if( rth < 0 || rth >= row || cth < 0 || cth >= col ) return; if( visited[rth][cth] ) return; count++; visited[rth][cth] = true; res.push_back( matrix[rth][cth] ); switch(flag) { case 0:{cth++;move( matrix, 0 );break;}//right case 1:{rth++;move( matrix, 1 );break;}//down case 2:{cth--;move( matrix, 2 );break;}//left case 3:{rth--;move( matrix, 3 );break;}//up } return; } };

方法二

1、由于是以从外圈到内圈的顺序依次打印，所以我们可以将这个矩阵看为一圈一圈的。每次打印一圈，然后想办法解决每一圈是如何打印的。

打印的起点：最外圈打印的起点当然是左上角的那个点，坐标为（0，0）。然后下一圈起点很明显是（1, 1），再下一圈就是（2, 2）。我们发现了规律，每次打印的起点的 x 坐标和 y 坐标相等，依次加一；然后需要判断结束条件：我们可以发现，当矩阵是6*6的矩阵，它的最内圈的起点坐标为（2, 2），并且，横坐标的2倍小于6，纵坐标的2倍也下于6。如果矩阵是4*4的，它最内圈的起点是（1, 1），并且横坐标的2倍小于4，纵坐标的2倍也小于4。再比如，某个矩阵只有一个点，1*1矩阵，它最内圈的起点是（0，0），并且横坐标的2倍小于1，纵坐标的2倍也小于1。假设这个起点坐标为（start，start），所以我们就发现，循环继续的条件是start*2<rows,start*2<cols。

2、如何打印一圈：

显然我们可以把打印一圈分为四步：第一步从左到右打印一行，第二步从上到下打印一列，第三步从右到左打印一行，第四步从下到上打印一列。 不过，最后一圈有可能会退化成只有一行，只有一列，甚至只有一个数字。因此打印也退化成了三步或两步或一步。因此打印前要分析好每一步的前提条件。 第一步总是需要的。第二步需要判断终止行号大于起始行号。第三步需要终止行号大于起始行号以及终止列小于起始列号。第四步需要至少有三行两列，因此要求终止行号比起始行号至少大2,同时终止行号大于起始列号。

代码

void PrintMatrixClockwisely(int** numbers, int columns, int rows) { if(numbers == nullptr || columns <= 0 || rows <= 0) return; int start = 0; while(columns > start * 2 && rows > start * 2) { PrintMatrixInCircle(numbers, columns, rows, start); ++start; } } void PrintMatrixInCircle(int** numbers, int columns, int rows, int start) { int endX = columns - 1 - start; int endY = rows - 1 - start; // 从左到右打印一行 for(int i = start; i <= endX; ++i) { int number = numbers[start][i]; printNumber(number); } // 从上到下打印一列 if(start < endY) { for(int i = start + 1; i <= endY; ++i) { int number = numbers[i][endX]; printNumber(number); } } // 从右到左打印一行 if(start < endX && start < endY) { for(int i = endX - 1; i >= start; --i) { int number = numbers[endY][i]; printNumber(number); } } // 从下到上打印一行 if(start < endX && start < endY - 1) { for(int i = endY - 1; i >= start + 1; --i) { int number = numbers[i][start]; printNumber(number); } } } void printNumber(int number) { printf("%d\t", number); }