力扣-54. 螺旋矩阵

1.题目

题目地址(54. 螺旋矩阵 - 力扣（LeetCode）)

https://leetcode.cn/problems/spiral-matrix/

题目描述

给你一个 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

2.题解

2.1 模拟(图论 + 标记)

思路

使用图论中的方向数组表示方向, 使用标记数组visited标识哪些元素被访问过了,一旦遇到边界或者遇到被访问过的标记就转向即可
标记方式不止一种, 这里也可以直接将遍历过的元素取负值或者赋值为INT_MAX均可

注意判断这里: if(dx < 0 || dx >= row || dy < 0 || dy >= col || visited[dx][dy])
一定要使用熔断机制, 将visited[dx][dy] 放在最后, 否则就会发生数组越界!!!

代码

• 语言支持：C++

C++ Code:

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int row = matrix.size(), col = matrix[0].size();vector<vector<int>> visited(row, vector<int>(col, 0));vector<pair<int, int>> dir{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int cnt = 0, x = 0, y = 0;vector<int> ans;for(int i = 0; i < row * col; i++){ans.push_back(matrix[x][y]);visited[x][y] = 1;int dx = x + dir[cnt].first;int dy = y + dir[cnt].second; if(dx < 0 || dx >= row || dy < 0 || dy >= col || visited[dx][dy]){cnt = (cnt + 1) % 4;dx = x + dir[cnt].first;dy = y + dir[cnt].second; }x = dx;y = dy;}return ans;}
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：\(O(m * n)\)
• 空间复杂度：\(O(m * n)\)

2.2

思路

可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。
定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如，下图矩阵最外层元素都是第 1 层，次外层元素都是第 2 层，剩下的元素都是第 3 层。
每一层的rowBegin, rowEnd, colBegin, colEnd都不同, 每次遍历完一行/一列便更新即可!

代码

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int rowBegin = 0, rowEnd = matrix.size() - 1;    // 行int colBegin = 0, colEnd = matrix[0].size() - 1; // 列vector<int> ans;while (true) {// 从左向右遍历(行)for (int i = colBegin; i <= colEnd; i++)ans.push_back(matrix[rowBegin][i]); // rowBegin 这行已经遍历过了,// 下次不可以再遍历, ++rowBeginif (++rowBegin > rowEnd)break;// 从上向下遍历(列)for (int i = rowBegin; i <= rowEnd; i++)ans.push_back(matrix[i][colEnd]); // colEnd 这列已经遍历过了,// 下次不可以再遍历, --colEndif (--colEnd < colBegin)break;// 从右向左遍历(行)for (int i = colEnd; i >= colBegin; i--)ans.push_back(matrix[rowEnd][i]);if (--rowEnd < rowBegin)break;// 从下向上遍历(列)for (int i = rowEnd; i >= rowBegin; i--)ans.push_back(matrix[i][colBegin]);if(++colBegin > colEnd)break;}return ans;}
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：\(O(m * n)\)
• 空间复杂度：\(O(1)\)