当前位置：首页 > news >正文

力扣最热一百题——螺旋矩阵

news 来源：原创 2024/9/21 1:37:51

题目链接：54. 螺旋矩阵 - 力扣（LeetCode）

题目描述

示例

提示：

解法一：模拟

1. 边界初始化

2. 循环遍历矩阵

3. 从左到右遍历上边界

4. 从上到下遍历右边界

5. 从右到左遍历下边界

6. 从下到上遍历左边界

7. 结束条件

代码执行流程总结

Java写法：

运行时间以及内存消耗

C++写法：

运行时间以及内存消耗

总结

题目链接：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;}
};