首页 > 代码库 > LeetCode[Array]: Spiral Matrix
LeetCode[Array]: Spiral Matrix
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<int> spiralOrder(vector<vector<int> > &matrix) {
vector<int> 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<int> inner = spiralOrder(matrix);
result.insert(result.end(), inner.begin(), inner.end());
return result;
}
后来在Discuss上逛了逛,发现这个题其实用迭代来解会更好,因为迭代不需要将矩阵缩小,直接用4个变量标志顶部扫描到哪一行、右边扫描到哪一列、底部扫描到哪一行、左边扫描到哪一列,然后每迭代一次完成一环的扫描。具体实现可以参考这里。
LeetCode[Array]: Spiral Matrix
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。