Spiral Matrix
程序员文章站
2022-07-12 09:29:51
...
1,题目要求
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output:[1,2,3,4,8,12,11,10,9,5,6,7]
给定m×n个元素的矩阵(m行,n列),以螺旋顺序返回矩阵的所有元素。
2,题目思路
对于这道题,要求将一个矩阵按照螺旋顺时针顺序展开为一维数组。
在展开数组时,我们可以看到,我们按照的顺序是:
- 向右->向下->向左->向上
假如说一个矩阵是m*n的,那么,首先向右走m步,然后向下走n-1步;接着向左走m-1步,之后向上走n-2步。。。
当我们发现需要走的步数为0时,自然就结束了。
具体思路见代码的注释部分。
3,代码实现
static auto speedup = [](){
ios::sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
int nr = matrix.size();
if(nr == 0)
return {};
int nc = matrix[0].size();
if(nc == 0)
return {};
//设定走的步数
//初始先向右走nc步,再向下走nr-1步
vector<int> nSteps {nc, nr-1};
int iDir = 0; //方向指示的下标
int ir = 0, ic = -1; //初值设置为-1,是因为要走nc步
//iDir偶数下标,说明是横向的走;奇数下标,说明是竖向走
//只要走的步骤为0,说明就结束了
//nSteps[iDir%2]表示当前要走的步骤数
while(nSteps[iDir%2]){
for(int i = 0;i<nSteps[iDir%2];i++){
ir += dirs[iDir][0]; //更新横坐标
ic += dirs[iDir][1]; //更新纵坐标
res.push_back(matrix[ir][ic]);
}
nSteps[iDir%2]--; //减少下一次该方向(实际是反方向)所要走的步数
iDir = (iDir + 1)%4;
}
return res;
}
private:
//定义方向,分别是向右、向下、向左、向上
vector<vector<int>> dirs{{0,1},{1,0},{0,-1},{-1,0}};
};
上一篇: 剑指offer--构建乘法数组
下一篇: Spiral Matrix