用分享的方式成长,用有趣的眼光看世界。
欢迎来到12 26 25的博客 !
热爱编码、算法、知识总结,不定期更新有趣、有料、有营养内容。 让我们共同学习,共同进步。
分类:数组, 模拟
难度: 中等
老规矩,先上AC图:
给你一个 m
行 n
列的矩阵 matrix
,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
示例 1:
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]
示例 2:
输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
题解:
首先读题,题目中给到的序列是一个数组图,我们需要按照顺时针方向逐个遍历数据,并输出。
分析题意首先我们必须遍历所有元素,所以最小时间复杂度O(N),另外数据量并不高,所以可以采用直接模拟方法,主要考察代码能力。
首先设定上下左右边界,之后按照➡⬇⬅⬆的顺序依次遍历,需要考虑到终止条件和状态更新。
1. 向右移动到最右,此时这一行因为已经使用过了,可以将其从图中删去,重新定义上边界top++
2. 向下移动到最下,此时这一列因为已经使用过了,可以将其从图中删去,重新定义右边界right--
3. 向左移动到最左,此时这一行因为已经使用过了,可以将其从图中删去,重新定义下边界bottom--
4. 向上移动到最上,此时这一列因为已经使用过了,可以将其从图中删去,重新定义右边界left++
状态更新后时刻判断新状态,若上下界限交错,则上下遍历完成,左右同理。同时完成即为结束。
时间复杂度: O(N); 空间复杂度 O(N).
代码如下:
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> result;
int left = 0, right = matrix[0].size() - 1, top = 0, bottom = matrix.size() - 1;
while(left <= right && top <= bottom){
if(top <= bottom){
for(int i = left; i <= right; i++) result.push_back(matrix[top][i]);
top++;
}
if(left <= right){
for(int i = top; i <= bottom; i++) result.push_back(matrix[i][right]);
right--;
}
if(top <= bottom){
for(int i = right; i >= left; i--) result.push_back(matrix[bottom][i]);
bottom--;
}
if(left <= right){
for(int i = bottom; i >= top; i--) result.push_back(matrix[i][left]);
left++;
}
}
return result;
}
};
上一篇: 从B站 (哔哩哔哩) 泄露的源码里发现了B站视频推荐的秘密
下一篇: 400+条实用C/C++框架、库、工具整理 ,你能想到的都在这里了
如果有什么要补充的,欢迎下方
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)