能看的网站_都市快报西安疫情最新消息_烟台网络推广_站长工具 seo综合查询

螺旋顺序遍历矩阵

问题描述

这题和之前的顺时针旋转矩阵很像，我又重新思考了一遍。
给定一个 m x n 的矩阵，要求按螺旋顺序（从外层到内层，顺时针方向）遍历矩阵的所有元素，并将结果存储在一个数组中。螺旋顺序的遍历方式如下：

1. 从左到右遍历上边界。
2. 从上到下遍历右边界。
3. 从右到左遍历下边界。
4. 从下到上遍历左边界。

重复上述步骤，直到遍历完整个矩阵。

示例

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

约束条件

• matrixSize 表示矩阵的行数。
• matrixColSize 表示矩阵的列数。
• returnSize 用于返回结果数组的大小。
• 矩阵的行数和列数在 [1, 200] 范围内。

---

问题分析

螺旋顺序遍历矩阵的关键在于逐层遍历矩阵的外圈，并逐步向内收缩。直接遍历矩阵可能会导致边界条件混乱，因此需要一种系统的方法来管理边界。

难点分析

1. 边界管理：如何正确管理上下左右边界，避免重复遍历或遗漏某些元素。
2. 终止条件：如何判断何时结束遍历。
3. 内存分配：如何动态分配内存并返回结果数组。

解题思路

我们可以通过以下步骤实现螺旋顺序遍历：

1. 初始化边界：

   • 定义矩阵的上下左右边界：top、bottom、left 和 right。

2. 逐层遍历：

   • 按顺时针方向依次遍历当前层的四个方向：
     1. 从左到右（上边界）。
     2. 从上到下（右边界）。
     3. 从右到左（下边界）。
     4. 从下到上（左边界）。
   • 每遍历完一层后，收缩边界。

3. 终止条件：

   • 当上下边界或左右边界交叉时，停止遍历。

4. 返回结果：

   • 将结果数组的大小存入 returnSize，并返回结果数组。

---

代码实现

以下是完整的 C 代码实现，包含详细注释：

/*** 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 m = matrixSize;          // 矩阵的行数int n = matrixColSize[0];    // 矩阵的列数int total = m * n;           // 矩阵元素总数int* result = (int*)malloc(total * sizeof(int));  // 分配结果数组*returnSize = total;         // 设置返回数组的大小int top = 0, bottom = m - 1;  // 上下边界int left = 0, right = n - 1;  // 左右边界int index = 0;                // 结果数组的索引// 螺旋顺序遍历矩阵while (top <= bottom && left <= right) {// 从左到右遍历上边界for (int i = left; i <= right; i++) {result[index++] = matrix[top][i];  // 将当前元素加入结果数组}top++;  // 上边界收缩// 从上到下遍历右边界for (int i = top; i <= bottom; i++) {result[index++] = matrix[i][right];  // 将当前元素加入结果数组}right--;  // 右边界收缩// 从右到左遍历下边界if (top <= bottom) {  // 防止重复遍历for (int i = right; i >= left; i--) {result[index++] = matrix[bottom][i];  // 将当前元素加入结果数组}bottom--;  // 下边界收缩}// 从下到上遍历左边界if (left <= right) {  // 防止重复遍历for (int i = bottom; i >= top; i--) {result[index++] = matrix[i][left];  // 将当前元素加入结果数组}left++;  // 左边界收缩}}return result;  // 返回结果数组
}

代码说明

1. 边界初始化：

   • 定义矩阵的上下左右边界，分别用 top、bottom、left 和 right 表示。

2. 逐层遍历：

   • 按顺时针方向依次遍历当前层的四个方向，并将元素存入结果数组。
   • 每遍历完一层后，收缩对应的边界。

3. 终止条件：

   • 当上下边界或左右边界交叉时，停止遍历。

4. 结果数组：

   • 分配动态内存存储结果，并将结果数组的大小存入 returnSize。

---

测试用例

以下是几个测试用例及其结果：

测试用例 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]

测试用例 3

输入：

matrix = [[1, 2],[3, 4]
]

输出：

[1, 2, 4, 3]

---

总结

通过逐层遍历矩阵的外圈并逐步收缩边界，我们实现了按螺旋顺序遍历矩阵的功能。这种方法的时间复杂度为 O(m × n)，空间复杂度为 O(1)（不考虑返回数组的存储空间）。