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].
一开始这个题目我想到的是用递归来做：首先扫描最外环并缩小矩阵，然后递归调用内部矩阵来完成整个矩阵的扫描。
扫描最外环并缩小矩阵的具体过程是：首先扫描第一行，扫描完去掉第一行；扫描最后一列，扫描的同时去掉最后一列；逆向扫描最后一行，扫描完去掉最后一行；逆向扫描第一列，扫描同时去掉第一列。这样扫描完成时矩阵也变小了，递归调用继续扫描变小的矩阵，直到所有元素都扫描完时即可。
根据以上思路，我的C++代码实现如下：
vector
spiralOrder(vector
> &matrix) { vector
result; if (matrix.empty()) return result; // scan the first row result = matrix[0]; matrix.erase(matrix.begin()); if (matrix.empty()) return result; // scan the last col int colIdx = matrix[0].size() - 1; for (int i = 0; i < matrix.size(); ++i) { result.push_back(matrix[i][colIdx]); matrix[i].erase(matrix[i].begin() + colIdx); } if (matrix[0].empty()) return result; // scan the last row result.insert(result.end(), matrix.back().rbegin(), matrix.back().rend()); matrix.erase(matrix.end() - 1); if (matrix.empty()) return result; // scan the first col for (int i = matrix.size() - 1; i >= 0; --i) { result.push_back(matrix[i][0]); matrix[i].erase(matrix[i].begin()); } if (matrix[0].empty()) return result; // scan the inner matrix vector
inner = spiralOrder(matrix); result.insert(result.end(), inner.begin(), inner.end()); return result; }
后来在Discuss上逛了逛，发现这个题其实用迭代来解会更好，因为迭代不需要将矩阵缩小，直接用4个变量标志顶部扫描到哪一行、右边扫描到哪一列、底部扫描到哪一行、左边扫描到哪一列，然后每迭代一次完成一环的扫描。具体实现可以参考这里。