当前位置：首页 > news >正文

【ARTS】【LeetCode-59】螺旋矩阵

news 2025/6/8 5:22:35

前言

仅做学习使用，侵删

后面计划做LeetCode 100热题

什么是ARTS？

算法(Algorithm): 每周至少一道LeetCode算法题，加强编程训练和算法学习

阅读(Review)：阅读并点评至少一篇英文技术文章，提高英文水平

技巧 (Tip)：学习至少一个技术技巧，总结、归纳日常工作中遇到的知识点

分享(Share)：分析一篇有关点和思考的技术文章，建立影响力，输出价值观

算法(Algorithm)

力扣第59题

59. 螺旋矩阵 II - 力扣（LeetCode）

题目描述

给你一个正整数 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 int[][] generateMatrix(int n) {int[][] nums = new int[n][n];int startX = 0, startY = 0;  // 每一圈的起始点int offset = 1;int count = 1;  // 矩阵中需要填写的数字int loop = 1; // 记录当前的圈数int i, j; // j 代表列, i 代表行;while (loop <= n / 2) {// 顶部// 左闭右开，所以判断循环结束时， j 不能等于 n - offsetfor (j = startY; j < n - offset; j++) {nums[startX][j] = count++;}// 右列// 左闭右开，所以判断循环结束时， i 不能等于 n - offsetfor (i = startX; i < n - offset; i++) {nums[i][j] = count++;}// 底部// 左闭右开，所以判断循环结束时， j != startYfor (; j > startY; j--) {nums[i][j] = count++;}// 左列// 左闭右开，所以判断循环结束时， i != startXfor (; i > startX; i--) {nums[i][j] = count++;}startX++;startY++;offset++;loop++;}if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值nums[startX][startY] = count;}return nums;}
}

时间复杂度：

O(n2)，其中 n 是给定的正整数。矩阵的大小是 n×n，需要填入矩阵中的每个元素。

即：模拟遍历二维矩阵的时间

空间复杂度：

O(1)。除了返回的矩阵以外，空间复杂度是常数。

以下是LeetCode官方题解

方法二：按层模拟

思想：

可以将矩阵看成若干层，首先填入矩阵最外层的元素，其次填入矩阵次外层的元素，直到填入矩阵最内层的元素。

定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如，下图矩阵最外层元素都是第 1 层，次外层元素都是第 2 层，最内层元素都是第 3 层。

[[1, 1, 1, 1, 1, 1],[1, 2, 2, 2, 2, 1],[1, 2, 3, 3, 2, 1],[1, 2, 3, 3, 2, 1],[1, 2, 2, 2, 2, 1],[1, 1, 1, 1, 1, 1]
]

对于每层，从左上方开始以顺时针的顺序填入所有元素。假设当前层的左上角位于 (top,left)，右下角位于 (bottom,right)，按照如下顺序填入当前层的元素。

1. 从左到右填入上侧元素，依次为 (top,left) 到 (top,right)。
2. 从上到下填入右侧元素，依次为 (top+1,right) 到 (bottom,right)。
3. 如果 left<right 且 top<bottom，则从右到左填入下侧元素，依次为 (bottom,right−1) 到(bottom,left+1)，以及从下到上填入左侧元素，依次为 (bottom,left) 到 (top+1,left)。

填完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续填入元素，直到填完所有元素为止。

class Solution {public int[][] generateMatrix(int n) {int num = 1;int[][] matrix = new int[n][n];int left = 0, right = n - 1, top = 0, bottom = n - 1;while (left <= right && top <= bottom) {for (int column = left; column <= right; column++) {matrix[top][column] = num;num++;}for (int row = top + 1; row <= bottom; row++) {matrix[row][right] = num;num++;}if (left < right && top < bottom) {for (int column = right - 1; column > left; column--) {matrix[bottom][column] = num;num++;}for (int row = bottom; row > top; row--) {matrix[row][left] = num;num++;}}left++;right--;top++;bottom--;}return matrix;}
}