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

代码训练LeetCode(44)螺旋矩阵

news 2025/7/3 18:17:53

代码训练(44)螺旋矩阵

Author: Once Day Date: 2025年7月2日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

3. 无重复字符的最长子串 - 力扣（LeetCode）
力扣 (LeetCode) 全球极客挚爱的技术成长平台

文章目录

- - 代码训练(44)螺旋矩阵
  - - 1. 原题
    - 2. 分析
    - 3. 代码实现
    - 4. 总结

1. 原题

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

提示：

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

示例 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]

2. 分析

假设你有一个矩阵（二维数组），它是由 m 行和 n 列组成的。你的任务是按照顺时针方向螺旋地遍历这个矩阵，并返回一个包含矩阵所有元素的数组。

这个问题要求我们从外围开始，一层层地向内部遍历矩阵。具体来说，你需要从最外层的左上角开始，按顺时针方向环绕矩阵边缘，直到达到矩阵的中心。

解题思路：

初始化边界: 定义四个变量来跟踪当前未遍历的矩阵的边界：top, bottom, left, right。初始时，top = 0, bottom = m-1, left = 0, right = n-1。
遍历矩阵: 使用一个循环来遍历矩阵，每完成一圈后，相应地调整边界条件（top++, bottom–, left++, right–）。
从左到右: 遍历顶部行从左边界到右边界。
从上到下: 遍历右边界的列从顶部到底部。
从右到左: 如果还存在更多的行，遍历底部行从右边界到左边界。
从下到上: 如果还存在更多的列，遍历左边界的列从底部到顶部。
结束条件: 当 top > bottom 或 left > right 时，所有元素都遍历完成。

例如，给定矩阵：

1   2   3
4   5   6
7   8   9

第一圈: 输出1, 2, 3 然后 6, 9 然后 8, 7 最后 4。
第二圈: 只剩下 5，输出 5。

性能优化关键点:

内存优化: 直接使用一个足够大小的数组来存储结果，避免了使用动态数据结构可能带来的额外内存开销。
执行速度: 由于每个元素访问一次，算法的时间复杂度是 O(m*n)，这是最优的，因为每个元素至少需要被访问一次。

3. 代码实现

#include <stdio.h>
#include <stdlib.h>int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {if (matrixSize == 0 || matrixColSize[0] == 0) {*returnSize = 0;return NULL;}int m = matrixSize, n = matrixColSize[0];int* result = (int*)malloc(m * n * sizeof(int));int index = 0, top = 0, bottom = m - 1, left = 0, right = n - 1;while (top <= bottom && left <= right) {for (int col = left; col <= right; col++) {result[index++] = matrix[top][col];}for (int row = top + 1; row <= bottom; row++) {result[index++] = matrix[row][right];}if (top < bottom) {for (int col = right - 1; col >= left; col--) {result[index++] = matrix[bottom][col];}}if (left < right) {for (int row = bottom - 1; row > top; row--) {result[index++] = matrix[row][left];}}top++;bottom--;left++;right--;}*returnSize = index;return result;
}