跳到主要内容

螺旋矩阵

· 阅读需 4 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——54题​

💡 参考代码：​

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

/**
 * 按照顺时针螺旋顺序遍历矩阵
 * 
 * 解题思路：
 * 1. 使用四个边界变量控制遍历范围：上(top)、下(bottom)、左(left)、右(right)
 * 2. 按照顺时针方向依次遍历：从左到右 -> 从上到下 -> 从右到左 -> 从下到上
 * 3. 每完成一个方向的遍历，相应地收缩边界
 * 4. 当所有元素都被遍历完时停止
 * 
 * 时间复杂度: O(m*n) - 每个元素访问一次
 * 空间复杂度: O(1) - 除了结果数组外只使用常数额外空间
 */
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];     // 矩阵列数
    
    // 初始化结果数组
    *returnSize = m * n;
    int* result = (int*)malloc(sizeof(int) * (*returnSize));
    
    // 初始化四个边界
    int top = 0;      // 上边界
    int bottom = m - 1;  // 下边界
    int left = 0;     // 左边界
    int right = n - 1;   // 右边界
    
    int index = 0;    // 结果数组索引
    
    // 当还有未遍历的元素时继续循环
    while (top <= bottom && left <= right) {
        // 1. 从左到右遍历上边界
        for (int j = left; j <= right; j++) {
            result[index++] = matrix[top][j];
        }
        top++;  // 上边界下移
        
        // 2. 从上到下遍历右边界
        for (int i = top; i <= bottom; i++) {
            result[index++] = matrix[i][right];
        }
        right--;  // 右边界左移
        
        // 3. 从右到左遍历下边界（如果还有行需要遍历）
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {
                result[index++] = matrix[bottom][j];
            }
            bottom--;  // 下边界上移
        }
        
        // 4. 从下到上遍历左边界（如果还有列需要遍历）
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                result[index++] = matrix[i][left];
            }
            left++;  // 左边界右移
        }
    }
    
    return result;
}

📖 总结：​

点击展开题目总结

🤔 螺旋矩阵

1️⃣ 题目核心信息​

🎯 功能描述：按照顺时针螺旋顺序遍历矩阵中的所有元素并返回

📥 输入输出：

  • 输入：
    • matrix: 二维整数数组（矩阵）
    • matrixSize: 矩阵行数 m
    • matrixColSize: 每行列数的数组（这里 n = matrixColSize[0]）
  • 输出：
    • 返回包含所有元素的整数数组，按顺时针螺旋顺序排列
    • returnSize: 输出数组的长度（通过指针返回）

2️⃣ 实现原理​

💡 核心思路：使用边界控制法，通过维护四个边界变量来模拟顺时针螺旋遍历过程

📋 实现步骤：

  1. 初始化四个边界变量：上(top)、下(bottom)、左(left)、右(right)
  2. 按照顺时针方向依次遍历：从左到右 → 从上到下 → 从右到左 → 从下到上
  3. 每完成一个方向的遍历，相应地收缩边界
  4. 重复步骤2-3直到所有元素都被遍历完

3️⃣ 关键点解析​

🎯 代码技巧​

  • 边界控制：使用四个变量精确控制遍历范围，避免重复访问
  • 方向循环：严格按照右→下→左→上的顺序遍历
  • 边界检查：在遍历行和列之前检查边界有效性，处理非方形矩阵
  • 边界收缩：每完成一个方向遍历后及时更新边界

4️⃣ 使用场景​

✅ 适用情况：​

  • 矩阵螺旋遍历相关问题
  • 二维数组的特殊遍历模式
  • 需要按特定顺序访问矩阵元素的场景

⚠️ 前提条件：​

  • 输入矩阵不为空
  • 矩阵行列数在有效范围内

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(m×n)，其中 m 是行数，n 是列数，每个元素只访问一次

  • 💾 空间复杂度：O(1)，除了结果数组外只使用常数额外空间

6️⃣ 注意事项​

🚩 边界情况：​

  • 空矩阵：matrixSize == 0 或 matrixColSize[0] == 0
  • 单行矩阵：只有一行需要特殊处理
  • 单列矩阵：只有一列需要特殊处理
  • 奇数大小矩阵：中心元素的正确访问

💥 易错点：​

  • 忘记在遍历完一行或一列后检查边界是否仍然有效
  • 边界收缩的顺序错误导致重复访问元素
  • 没有正确处理非方形矩阵（如3×4矩阵）
  • 忘记为返回数组分配内存或计算错误的数组大小
加载评论中...