力扣第 54 题 **螺旋矩阵**

力扣第 54 题是 螺旋矩阵（Spiral Matrix）。题目要求按螺旋顺序遍历一个 m x n 的矩阵，并返回遍历的结果。

解题思路

螺旋矩阵的遍历顺序是 从左到右，然后 从上到下，接着 从右到左，最后 从下到上，依次循环，直到遍历完所有元素。可以通过定义边界条件来控制这些遍历方向：

1. 定义四个边界：上边界 top、下边界 bottom、左边界 left 和右边界 right。
2. 按照顺序进行遍历：
   • 从左到右遍历顶行。
   • 从上到下遍历最右列。
   • 从右到左遍历底行（若 top <= bottom）。
   • 从下到上遍历最左列（若 left <= right）。
3. 每完成一行或一列的遍历后，更新相应的边界。
4. 重复上述步骤，直到 top > bottom 或 left > right，即所有元素都被访问。

C 语言实现

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

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    if (matrixSize == 0 || matrixColSize[0] == 0) {
        *returnSize = 0;
        return NULL;
    }

    int top = 0, bottom = matrixSize - 1;
    int left = 0, right = matrixColSize[0] - 1;
    int total = matrixSize * matrixColSize[0];
    
    int* result = (int*)malloc(total * sizeof(int));
    *returnSize = 0;

    while (top <= bottom && left <= right) {
        // 从左到右遍历顶行
        for (int i = left; i <= right; i++) {
            result[(*returnSize)++] = matrix[top][i];
        }
        top++;  // 顶行向下收缩

        // 从上到下遍历最右列
        for (int i = top; i <= bottom; i++) {
            result[(*returnSize)++] = matrix[i][right];
        }
        right--;  // 右列向左收缩

        // 从右到左遍历底行（确保尚未遍历过）
        if (top <= bottom) {
            for (int i = right; i >= left; i--) {
                result[(*returnSize)++] = matrix[bottom][i];
            }
            bottom--;  // 底行向上收缩
        }

        // 从下到上遍历最左列（确保尚未遍历过）
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                result[(*returnSize)++] = matrix[i][left];
            }
            left++;  // 左列向右收缩
        }
    }

    return result;
}

int main() {
    int rows = 3, cols = 3;
    int data[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int* matrix[3];
    for (int i = 0; i < rows; i++) {
        matrix[i] = data[i];
    }
    int matrixColSize[] = {3, 3, 3};
    int returnSize;

    int* result = spiralOrder(matrix, rows, matrixColSize, &returnSize);

    printf("螺旋顺序遍历结果: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    free(result);
    return 0;
}

逐步解释代码

1. 边界初始化：定义上、下、左、右边界，分别为 top = 0，bottom = matrixSize - 1，left = 0，right = matrixColSize[0] - 1。

2. 循环遍历：

   • 从左到右：遍历顶行，从 left 到 right，然后将 top 加 1。
   • 从上到下：遍历最右列，从 top 到 bottom，然后将 right 减 1。
   • 从右到左（若 top <= bottom）：遍历底行，从 right 到 left，然后将 bottom 减 1。
   • 从下到上（若 left <= right）：遍历最左列，从 bottom 到 top，然后将 left 加 1。

3. 返回结果：将所有遍历结果存入 result 数组，最终返回螺旋遍历结果。

复杂度分析

• 时间复杂度：$O(m\ast n)$，m 和 n 为矩阵的行数和列数。每个元素被访问一次。
• 空间复杂度：$O(m\ast n)$，存储螺旋顺序的结果数组需要 $O(m\ast n)$的空间。

原文地址：https://blog.csdn.net/weixin_48941116/article/details/143787613

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！