目录
题目链接:54. 螺旋矩阵 - 力扣(LeetCode)
注:下述题目描述和示例均来自力扣
题目描述
给你一个 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
解法一:模拟
按照顺时针方向从外圈到内圈依次读取矩阵中的元素。具体实现思路可以分为以下几个步骤:
1. 边界初始化
- 定义四个边界:
top
,bottom
,left
,right
,分别表示矩阵的上边界、下边界、左边界和右边界。 - 初始时,
top
为 0(最上方),bottom
为矩阵的最后一行索引,left
为 0(最左边),right
为矩阵的最后一列索引。
2. 循环遍历矩阵
- 进入
while
循环,条件是:top <= bottom && left <= right
。这意味着当矩阵还未完全遍历时,继续循环。 - 在每次循环中,按照四个方向依次遍历:从左到右、从上到下、从右到左、从下到上。每次遍历完一条边界后,收缩该边界(即移动内圈的边界)。
3. 从左到右遍历上边界
- 首先,遍历当前
top
行,从left
到right
,将该行的所有元素依次添加到结果数组中。 - 遍历完成后,将
top
变量加 1,表示上边界下移一行,进入内层。
4. 从上到下遍历右边界
- 然后,遍历当前
right
列,从top
到bottom
,将该列的所有元素依次添加到结果数组中。 - 遍历完成后,将
right
变量减 1,表示右边界左移一列。
5. 从右到左遍历下边界
- 如果
top <= bottom
仍然成立(即还有未遍历的行),开始遍历bottom
行,从right
到left
,将该行的所有元素依次添加到结果数组中。 - 遍历完成后,将
bottom
变量减 1,表示下边界上移一行。
6. 从下到上遍历左边界
- 如果
left <= right
仍然成立(即还有未遍历的列),开始遍历left
列,从bottom
到top
,将该列的所有元素依次添加到结果数组中。 - 遍历完成后,将
left
变量加 1,表示左边界右移一列。
7. 结束条件
- 循环不断缩小边界,直到
top > bottom
或left > right
,表示已经遍历完所有的元素,此时退出循环。 - 返回保存螺旋顺序的
res
数组。
代码执行流程总结
- 每次从四个方向依次遍历矩阵的当前边界。
- 每遍历完一条边界,收缩该边界,进入下一层的螺旋圈。
- 重复上述步骤,直到所有元素都被遍历完。
Java写法:
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return res;
}
int top = 0; // 上边界
int bottom = matrix.length - 1; // 下边界
int left = 0; // 左边界
int right = matrix[0].length - 1; // 右边界
while (top <= bottom && left <= right) {
// 从左到右遍历当前的上边界
for (int i = left; i <= right; i++) {
res.add(matrix[top][i]);
}
top++; // 上边界收缩
// 从上到下遍历当前的右边界
for (int i = top; i <= bottom; i++) {
res.add(matrix[i][right]);
}
right--; // 右边界收缩
// 判断是否还需要遍历
if (top <= bottom) {
// 从右到左遍历当前的下边界
for (int i = right; i >= left; i--) {
res.add(matrix[bottom][i]);
}
bottom--; // 下边界收缩
}
// 判断是否还需要遍历
if (left <= right) {
// 从下到上遍历当前的左边界
for (int i = bottom; i >= top; i--) {
res.add(matrix[i][left]);
}
left++; // 左边界收缩
}
}
return res;
}
}
运行时间以及内存消耗
C++写法:
#include <vector>
using namespace std;
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
if (matrix.empty() || matrix[0].empty()) {
return res;
}
int top = 0; // 上边界
int bottom = matrix.size() - 1; // 下边界
int left = 0; // 左边界
int right = matrix[0].size() - 1; // 右边界
while (top <= bottom && left <= right) {
// 从左到右遍历当前的上边界
for (int i = left; i <= right; i++) {
res.push_back(matrix[top][i]);
}
top++; // 上边界收缩
// 从上到下遍历当前的右边界
for (int i = top; i <= bottom; i++) {
res.push_back(matrix[i][right]);
}
right--; // 右边界收缩
// 判断是否还需要遍历
if (top <= bottom) {
// 从右到左遍历当前的下边界
for (int i = right; i >= left; i--) {
res.push_back(matrix[bottom][i]);
}
bottom--; // 下边界收缩
}
// 判断是否还需要遍历
if (left <= right) {
// 从下到上遍历当前的左边界
for (int i = bottom; i >= top; i--) {
res.push_back(matrix[i][left]);
}
left++; // 左边界收缩
}
}
return res;
}
};
运行时间以及内存消耗
总结
这里的边界条件实在是非常的难把握,所实话,一但掉入了边界条件的陷阱之后就会让你一直缝缝补补,很难有几率能缝缝补补出来。
正如那句话所说:一如入循环深似海,从此offer是路人
标签:遍历,matrix,bottom,top,矩阵,最热,力扣,left,边界 From: https://blog.csdn.net/DDDDWJDDDD/article/details/142283998