Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
You should return [1,2,3,6,9,8,7,4,5]
.
这道题让我们将一个矩阵按照螺旋顺序打印出来,我们只能一条边一条边的打印,首先我们要从给定的mxn的矩阵中算出按螺旋顺序有几个环,注意最终间的环可以是一个数字,也可以是一行或者一列。环数的计算公式是 min(m, n) / 2,知道了环数,我们可以对每个环的边按顺序打印,比如对于题目中给的那个例子,个边生成的顺序是(用颜色标记了数字) Red -> Green -> Blue -> Yellow -> Black
1 2 3
4 5 6
7 8 9
我们定义p,q为当前环的高度和宽度,当p或者q为1时,表示最后一个环只有一行或者一列,可以跳出循环。此题的难点在于下标的转换,如何正确的转换下标是解此题的关键,我们可以对照着上面的3x3的例子来完成下标的填写,代码如下:
class Solution { public: vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int> res; if (matrix.empty() || matrix[0].empty()) return res; int m = matrix.size(), n = matrix[0].size(); int c = m > n ? (n + 1) / 2 : (m + 1) / 2; int p = m, q = n; for (int i = 0; i < c; ++i, p -= 2, q -= 2) { for (int col = i; col < i + q; ++col) res.push_back(matrix[i][col]); for (int row = i + 1; row < i + p; ++row) res.push_back(matrix[row][i + q - 1]); if (p == 1 || q == 1) break; for (int col = i + q - 2; col >= i; --col) res.push_back(matrix[i + p - 1][col]); for (int row = i + p - 2; row > i; --row) res.push_back(matrix[row][i]); } return res; } };
本文转自博客园Grandyang的博客,原文链接:螺旋矩阵[LeetCode] Spiral Matrix ,如需转载请自行联系原博主。