文章

[LeetCode] 每日一题 59. 螺旋矩阵 II

题目链接

https://leetcode.cn/problems/spiral-matrix-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

解题思路

本题要求生成一个 n x n 的矩阵,元素按顺时针螺旋顺序排列。通过模拟螺旋填充的过程,可以轻松得到答案。核心思路是通过一个方向数组来模拟矩阵中的填充过程,并且每次移动时检查是否可以继续在当前方向前进,若不能则转向

具体步骤如下:

  1. 方向数组:使用一个二维数组 dir 来表示四个方向:右、下、左、上

  2. 当前位置:使用 xy 变量表示当前位置,初始位置为矩阵的左上角 (0, 0)

  3. 填充过程:依次填充矩阵中的每个位置,直到所有位置都被填满。每填充一个位置后,通过判断下一个位置是否越界或已经填充过,决定是否改变填充方向

  4. 转向规则:当当前方向无法继续时,按照顺时针方向转向,依次循环右 -> 下 -> 左 -> 上

代码实现

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        // 依次是右下左上
        int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
        // x横坐标,y纵坐标
        int x = 0, y = 0;
        // 初始方向向右
        int d = 0;
        int index = 1;
        while (index <= n * n) {
            ans[y][x] = index;
            index++;
            int nextX = x + dir[d][0];
            int nextY = y + dir[d][1];
            if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n || ans[nextY][nextX] != 0) {
                d = (d + 1) % 4;
            }
            x += dir[d][0];
            y += dir[d][1];
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度:O(n^2),矩阵的大小是 n x n,因此需要填充 n^2 个位置,每个位置的填充操作是常数时间

  • 空间复杂度:O(n^2),需要一个 n x n 的矩阵来存储结果

总结

这道题本质上是一个经典的模拟题,主要考察对矩阵填充过程的理解。通过使用方向数组模拟顺时针的移动,并通过判断是否越界或已经填充过来决定是否转向,能够顺利实现螺旋填充。整体实现简单直接,适合使用模拟法解决

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0