1 题目描述

LCR 146. 螺旋遍历二维数组给定一个二维数组 array，任务是返回「螺旋遍历」该数组的结果。螺旋遍历是指从左上角开始，按照 向右、向下、向左、向上的顺序 依次提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。

2 解题思路

此题的关键在于理解螺旋遍历的过程。我们可以将整个过程分为四个方向：向右、向下、向左、向上。每完成一圈后，起始位置会向内移动一步，直到遍历完整个矩阵。

1. 初始化变量：
   • 定义起始坐标 startX 和 startY；
   • 定义偏移量 offset 用于记录已经遍历过的层数；
   • 定义循环次数 loop，它决定了需要进行几轮螺旋遍历；
   • 初始化结果数组 ans，其长度为 x * y，其中 x 和 y 分别为矩阵的行数和列数。
2. 遍历过程：
   • 每一轮遍历包括四个步骤（向右、向下、向左、向上）；
   • 根据 loop 的值确定是否还需要遍历中间剩余的部分。
3. 处理特殊情况：
   • 如果矩阵的行数大于或等于列数，最后剩下的部分是一列，需要从上到下遍历这一列；
   • 如果矩阵的行数小于列数，最后剩下的部分是一行，需要从左到右遍历这一行。

3 Java 代码实现

public class Solution {
    public int[] spiralArray(int[][] array) {
        if (array.length == 0 || array[0].length == 0) {
            return new int[0];
        }
        
        int startX = 0;
        int startY = 0;
        int offset = 1;
        int x = array.length;
        int y = array[0].length;
        int[] ans = new int[x * y];
        int loop = 1;
        int i, j;
        int index = 0;
        
        // 主循环遍历每一层
        while (loop <= Math.min(x, y) / 2) {
            // 向右遍历
            for (j = startY; j < y - offset; j++) {
                ans[index++] = array[startX][j];
            }
            // 向下遍历
            for (i = startX; i < x - offset; i++) {
                ans[index++] = array[i][j];
            }
            // 向左遍历
            for (; j > startY; j--) {
                ans[index++] = array[i][j];
            }
            // 向上遍历
            for (; i > startX; i--) {
                ans[index++] = array[i][j];
            }
            
            // 更新起始点和偏移量
            startX++;
            startY++;
            offset++;
            loop++;
        }
        
        // 处理剩余部分
        if (index < x * y) {
            if (x >= y) {
                for (i = startX; i <= x - offset; i++) {
                    ans[index++] = array[i][startY];
                }
            } else {
                for (j = startY; j <= y - offset; j++) {
                    ans[index++] = array[startX][j];
                }
            }
        }
        
        return ans;
    }
}

• 时间复杂度：O(mn)，其中 m 和 n 分别是矩阵的行数和列数。每个元素恰好被访问一次。
• 空间复杂度：O(1)（不考虑输出数组的空间），因为除了输出数组外，我们只使用了几个变量来存储边界和索引信息。

4 注意事项

• 边界条件处理：当数组的行数或列数为奇数时，需要特别处理中心点或剩余边的填充。
• 循环次数：循环的次数是 min(x, y) / 2，因为每次循环都会处理外圈的一层。
• 更新偏移量：随着循环的进行，需要不断更新偏移量 offset 和起始点 startX, startY。
• 索引更新：使用 index 变量来跟踪数组 ans 的当前位置，以便正确填充结果。