0%

[Leetcode]54. Spiral Matrix(C++)

题目描述

题目链接:54. Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

例子

例子 1

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

例子 2

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

解题思路

沿螺旋方向遍历矩阵,可以从外层开始遍历,每次遍历一圈,然后层层深入即可。在遍历一圈要注意各个方向的起点和边界。

代码如下:

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
#include <vector>

class Solution {
public:
std::vector<int> spiralOrder(std::vector<std::vector<int>>& matrix) {
std::vector<int> result;
int m = matrix.size();
int n = matrix[0].size();
int row1 = 0;
int row2 = m - 1;
int col1 = 0;
int col2 = n - 1;
while (row1 <= row2 && col1 <= col2) {
for (int c = col1; c <= col2; ++c) {
result.push_back(matrix[row1][c]);
}
for (int r = row1 + 1; r <= row2; ++r) {
result.push_back(matrix[r][col2]);
}
if (row1 < row2 && col1 < col2) {
for (int c = col2 - 1; c > col1; --c) {
result.push_back(matrix[row2][c]);
}
for (int r = row2; r > row1; --r) {
result.push_back(matrix[r][col1]);
}
}
row1++;
row2--;
col1++;
col2--;
}

return result;
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 54.SpiralMatrix.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions