分析
- 初始化变量：
- 使用
count 记录已访问的元素个数，初始为 0
- 将已访问的元素标记为
INF，以避免重复访问
- 初始化起始位置为
(x, y) = (0, -1)
- 按顺时针方向遍历：
- 按照 右、下、左、上 的顺序依次遍历矩阵
- 检查下一步是否越界或访问到标记值，如果满足条件则改变方向
- 收集结果：
- 返回结果：
- 当遍历的元素数量
count 等于矩阵元素总数时，返回结果
时间复杂度
需要遍历矩阵中的所有元素，总时间复杂度 O(n * m)
空间复杂度
在矩阵内原地标记访问过的元素，无需额外空间，空间复杂度为 O(1)
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
class Solution
{
public:
vector<int> spiralOrder(vector<vector<int>>& matrix)
{
int n = matrix.size(); // 矩阵行数
int m = matrix[0].size(); // 矩阵列数
int count = 0; // 记录访问过的元素数量
int INF = 0x3f3f3f3f; // 标记值，用于标记已访问的元素
std::vector<int> res; // 存放结果的数组
int x = 0, y = -1; // 起始位置在矩阵外部
while (count < n * m)
{
// 向右遍历
while (y + 1 < m && matrix[x][y + 1] != INF)
{
res.push_back(matrix[x][y + 1]); // 记录元素
matrix[x][y + 1] = INF; // 标记为已访问
++ y; // 移动列
++ count; // 更新已访问数量
}
// 向下遍历
while (x + 1 < n && matrix[x + 1][y] != INF)
{
res.push_back(matrix[x + 1][y]);
matrix[x + 1][y] = INF;
++ x;
++ count;
}
// 向左遍历
while (y - 1 >= 0 && matrix[x][y - 1] != INF)
{
res.push_back(matrix[x][y - 1]);
matrix[x][y - 1] = INF;
-- y;
++ count;
}
// 向上遍历
while (x - 1 >= 0 && matrix[x - 1][y] != INF)
{
res.push_back(matrix[x - 1][y]);
matrix[x - 1][y] = INF;
-- x;
++ count;
}
}
return res;
}
};
|
