力扣第59题螺旋矩阵 II

题目描述

给定一个正整数 n，生成一个 n x n 的矩阵，矩阵的填充顺序是螺旋顺序，具体如下：

• 从矩阵的左上角开始，依次向右、向下、向左、向上重复填充，直到所有位置填满。

解决思路

1. 初始化矩阵：

   • 创建一个二维数组，用于存储螺旋顺序生成的数字。
   • 设置初始值为 0。

2. 模拟螺旋填充：

   • 定义四个边界：上 (top)、下 (bottom)、左 (left)、右 (right)。
   • 按螺旋顺序逐层填充：
     • 从左到右填充顶部行。
     • 从上到下填充右边列。
     • 从右到左填充底部行。
     • 从下到上填充左边列。
   • 每填充一层后，收缩相应的边界。

3. 停止条件：

   • 当填充的数字超过 n^2 时停止。

C语言代码实现

#include <stdio.h>
#include <stdlib.h>

int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
    // Allocate memory for the matrix
    int** matrix = (int**)malloc(n * sizeof(int*));
    *returnColumnSizes = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        matrix[i] = (int*)malloc(n * sizeof(int));
        (*returnColumnSizes)[i] = n;
    }

    // Initialize boundaries
    int top = 0, bottom = n - 1, left = 0, right = n - 1;
    int num = 1; // Start filling from 1

    while (num <= n * n) {
        // Fill top row
        for (int i = left; i <= right; i++) {
            matrix[top][i] = num++;
        }
        top++;

        // Fill right column
        for (int i = top; i <= bottom; i++) {
            matrix[i][right] = num++;
        }
        right--;

        // Fill bottom row
        for (int i = right; i >= left; i--) {
            matrix[bottom][i] = num++;
        }
        bottom--;

        // Fill left column
        for (int i = bottom; i >= top; i--) {
            matrix[i][left] = num++;
        }
        left++;
    }

    *returnSize = n;
    return matrix;
}

int main() {
    int n = 3;
    int returnSize;
    int* returnColumnSizes;

    // Generate the spiral matrix
    int** result = generateMatrix(n, &returnSize, &returnColumnSizes);

    // Print the result
    printf("Spiral Matrix:\n");
    for (int i = 0; i < returnSize; i++) {
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d ", result[i][j]);
        }
        printf("\n");
        free(result[i]); // Free each row
    }

    // Free allocated memory
    free(result);
    free(returnColumnSizes);

    return 0;
}

运行结果

输入：

n = 3

输出：

Spiral Matrix:
1 2 3 
8 9 4 
7 6 5

复杂度分析

• 时间复杂度：O(n^2)，需要填充矩阵的每个元素。
• 空间复杂度：O(n^2)，用于存储结果矩阵。

代码逐行解释

int** matrix = (int**)malloc(n * sizeof(int*));

• 为结果矩阵动态分配空间，matrix 是一个指向指针的数组，每个指针将指向矩阵的一行。
• 总共分配了 n 个指针空间，用于存储 n 行。

*returnColumnSizes = (int*)malloc(n * sizeof(int));

• 为每一行的列数分配动态内存。returnColumnSizes 用于存储矩阵的列数数组。
• 由于矩阵是正方形，每一行的列数都是 n。

for (int i = 0; i < n; i++) {
    matrix[i] = (int*)malloc(n * sizeof(int));
    (*returnColumnSizes)[i] = n;
}

• 循环初始化矩阵的每一行：
  • 为矩阵的第 i 行分配空间，每行有 n 个整数。
  • 同时，设置 returnColumnSizes[i] = n，表示第 i 行有 n 列。

int top = 0, bottom = n - 1, left = 0, right = n - 1;
int num = 1; // Start filling from 1

• 初始化矩阵的边界：
  • top：当前待填充区域的顶部行索引。
  • bottom：当前待填充区域的底部行索引。
  • left：当前待填充区域的左侧列索引。
  • right：当前待填充区域的右侧列索引。
• num 是当前要填入矩阵的数字，从 1 开始。

while (num <= n * n) {

• 主循环条件：当要填入的数字 num 小于等于矩阵的总元素数 n * n 时，继续填充矩阵。

填充顶部行：

for (int i = left; i <= right; i++) {
    matrix[top][i] = num++;
}
top++;

• 从左到右填充当前 top 行的元素，left 到 right 列范围。
• 填充完成后，将 top 上移一行（top++），因为当前行已经填充完。

填充右侧列：

for (int i = top; i <= bottom; i++) {
    matrix[i][right] = num++;
}
right--;

• 从上到下填充当前 right 列的元素，top 到 bottom 行范围。
• 填充完成后，将 right 左移一列（right--），因为当前列已经填充完。

填充底部行：

for (int i = right; i >= left; i--) {
    matrix[bottom][i] = num++;
}
bottom--;

• 从右到左填充当前 bottom 行的元素，right 到 left 列范围。
• 填充完成后，将 bottom 上移一行（bottom--），因为当前行已经填充完。

填充左侧列：

for (int i = bottom; i >= top; i--) {
    matrix[i][left] = num++;
}
left++;

• 从下到上填充当前 left 列的元素，bottom 到 top 行范围。
• 填充完成后，将 left 右移一列（left++），因为当前列已经填充完。

更新返回值：

*returnSize = n;
return matrix;

• 设置返回的矩阵行数 returnSize = n。
• 返回构造好的二维数组 matrix。

完整执行流程

假设 n = 3，矩阵总共需要填充 3 x 3 = 9 个数字：

总结

• 通过动态调整边界，按照螺旋顺序依次填充矩阵。
• 使用 malloc 动态分配内存以存储矩阵结果和列大小。
• 注意内存释放，避免内存泄漏。