leetcode
leetcode 51 ~ 100
螺旋矩阵 II

螺旋矩阵 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

代码结果

运行时间: 52 ms, 内存: 14.9 MB


/* 
 * 题目思路:
 * 1. 使用流来生成螺旋矩阵较为复杂,因为流操作通常是单向的。这里我们仍然需要一个可变数据结构来存储矩阵的元素。
 * 2. 使用一个二维数组存储结果,并使用基本的数组操作来构建矩阵,同时将流的功能主要用于输出或处理结果。
 */
 
import java.util.Arrays;
import java.util.stream.Collectors;
 
public class Solution {
    public static int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int num = 1, top = 0, bottom = n - 1, left = 0, right = n - 1;
 
        while (num <= n * n) {
            // 从左到右
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;
            // 从上到下
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;
            // 从右到左
            for (int i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--;
            // 从下到上
            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }
 
        return matrix;
    }
 
    public static void main(String[] args) {
        int n = 3;
        int[][] matrix = generateMatrix(n);
        System.out.println(Arrays.stream(matrix)
                                 .map(Arrays::toString)
                                 .collect(Collectors.joining(",\n")));
    }
}
 

解释

方法:

这个题解采用了模拟螺旋填充的方式来生成矩阵。通过控制矩阵的上下左右边界,依次填充矩阵的外围元素。具体步骤如下: 1. 初始化一个 n x n 的矩阵,元素全部为0。 2. 初始化矩阵的上下左右边界 u、d、l、r。 3. 从左到右填充上边界,更新上边界 u。 4. 从上到下填充右边界,更新右边界 r。 5. 从右到左填充下边界,更新下边界 d。 6. 从下到上填充左边界,更新左边界 l。 7. 重复步骤3-6,直到填充完整个矩阵。

时间复杂度:

O(n^2)

空间复杂度:

O(n^2)

代码细节讲解

🦆
在初始化矩阵时,为什么选择将所有元素设为0,而不是其他默认值?
初始化矩阵时选择将所有元素设为0是因为0通常被视为一个清晰的占位符,它在视觉上容易区分已填充和未填充的区域。此外,0不在正整数范围内,这有助于在调试和验证过程中快速识别哪些位置尚未被更新。从实现的角度来看,使用列表推导式生成全0矩阵也是代码上的简洁实现。
🦆
在填充过程中,更新边界的操作比如`u += 1`或`r -= 1`是如何确保不会导致边界交叉,从而避免覆盖已填充的元素?
在填充过程中,每一次更新边界如`u += 1`或`r -= 1`之后,都会通过循环的条件检查(如`if u > d`或`if l > r`)来确保填充操作不会进入已填充的区域。每次填充完一个边界后立即更新这个边界,并检查新的边界值是否导致了边界交叉,如果交叉则终止循环,这样就确保了不会有覆盖已填充元素的风险。这种方法依赖于严格的顺序和边界更新逻辑,保证了操作的安全性。
🦆
题解中提到,当`u > d`或`l > r`时循环会中断,这种边界条件是如何确定的,它们能完全覆盖所有可能的情况吗?
这些边界条件是基于矩阵填充的逻辑确定的。在螺旋填充矩阵时,如果上边界`u`超过了下边界`d`,或者左边界`l`超过了右边界`r`,这意味着已没有剩余空间需要填充,因此循环可以安全地中断。这种检查确保了只要存在可填充的区域,循环就会继续执行。因为这个逻辑严格遵守了矩阵的空间约束,所以它能覆盖所有可能的情况,确保算法在任意有效输入下都能正确完成工作。
🦆
在函数返回值前没有进行任何额外的检查或调整,这是否意味着算法对所有有效输入(1 <= n <= 20)都能正确工作?
是的,算法在设计时已经考虑到了所有从1到20的有效输入。由于算法内部的边界条件和填充逻辑确保了每次操作都是在安全的范围内进行,且每个元素只被填充一次,因此不需要在函数返回值前进行任何额外的检查或调整。这保证了算法的正确性和完整性,使其能夠在所有指定范围内的输入上正确运行。

相关问题

螺旋矩阵

给你一个 mn 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

 

示例 1:

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

示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

 

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100