代码随想录二刷 ｜数组 ｜ 螺旋矩阵II

题目描述

29.螺旋矩阵II
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 20

解题思路 & 代码实现

本题不涉及具体的算法，比较考察对代码的掌控能力。

模拟顺时针画矩阵的过程：

• 填充上行从左到右
• 填充右侧从上到下
• 填充下行从右到左
• 填充左侧从下到上

由外向内一圈一圈画下去。

每一圈都要坚持左闭右开或左开右闭的原则，也就是说，坚持循环不变量的原则。

class Solution {
public:
	vector<vector<int>> generateMatrix(int n) {
		vector<vector<int>> result(n, vector<int>(n, 0));
		int startX = 0, startY = 0; // 每一次循环的起始位置
		int loop = n / 2; // 每个圈循环的次数
		int mid = n / 2; // 矩阵中间位置
		int count = 1; // 给矩阵中每一个空格赋值
		int offset = 1; // 控制每一条边的长度，每次循环都收缩一位
		int i, j;
		
		while (loop--) {
			i = startX;
			j = startY;

			// 填充上行从左到右
			for (j = startY; j < n - offset; j++) {
				res[startX][j] = count++;
			}
			// 填充右侧从上到下
			for (i = startX; i < n - offset; i++) {
				res[i][j] = count++;
			}			
			// 填充下行从右到左
			for (; j > startY; j--) {
				res[i][j] = count++;
			}
			// 填充左侧从下到上
			for (; i > startX; i--) {
				res[i][j] = count++;
			} 
			
			startX++;
			startY++;
			
			offset += 1;
		}
			if (n % 2) {
				res[mid][mid] = count;
			}
			return res;
	}
};
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

时间复杂度：O(n^2)
空间复杂度：O(1)