题目描述
题目链接:54. Spiral Matrix
Given an
m x n
matrix
, return all elements of thematrix
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
解题思路
沿螺旋方向遍历矩阵,可以从外层开始遍历,每次遍历一圈,然后层层深入即可。在遍历一圈要注意各个方向的起点和边界。
代码如下:
#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