0%

[Leetcode]59. Spiral Matrix II(C++)

题目描述

题目链接:59. Spiral Matrix II

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

例子

例子 1

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

例子 2

Input: n = 1
Output: [[1]]

Constraints

  • 1 <= n <= 20

解题思路

思路和 [Leetcode]54. Spiral Matrix(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
#include <vector>

class Solution {
public:
std::vector<std::vector<int>> generateMatrix(int n) {
std::vector<std::vector<int>> result(n, std::vector<int>(n, 0));
int row = 0;
int step = 1;
while (row < n / 2) {
for (int i = row; i < n - row - 1; ++i) {
result[row][i] = step;
step++;
}
for (int i = row; i < n - row - 1; ++i) {
result[i][n - row - 1] = step;
step++;
}
for (int i = n - 1 - row; i > row; --i) {
result[n - row - 1][i] = step;
step++;
}
for (int i = n - 1 - row; i > row; --i) {
result[i][row] = step;
step++;
}
row++;
}

if (n % 2 == 1) {
result[row][row] = step;
}

return result;
}
};
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n^2) —-> 返回值所需空间

GitHub 代码同步地址: 59.SpiralMatrixIi.cpp

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