[数组基础] 0054. 螺旋矩阵

1. 题目链接

0054. 螺旋矩阵 - 力扣

---

2. 题目大意

描述：给定一个 m×n大小的二维矩阵 matrix。

要求：按照顺时针旋转的顺序，返回矩阵中的所有元素。

说明：

• m==matrix.length。
• n==matrix[i].length。
• 1≤m,n≤10。
• −100≤matrix[i][j]≤100。

3. 示例

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

输入：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]

4. 解题思路

根据题意，我们从左上角 (0,0) 出发，按照「右下左上」的顺序前进：

---

首先向右走，如果到达矩阵边界，则向右转 90°，前进方向变为向下。

然后向下走，如果到达矩阵边界，则向右转 90°，前进方向变为向左。

然后向左走，如果到达矩阵边界，则向右转 90°，前进方向变为向上。

然后向上走，先从 7 走到 4，然后从 4 准备向上走，但上面的 1 是一个已经访问过的数字，
那么向右转 90°，前进方向变为向右。

重复上述过程，直到答案的长度为 mn。

---

方法一：标记

对于已经访问过的数字，可将其标记为 ∞ ，从而避免重复访问。

用一个长为 4 的方向数组 DIRS=[(0,1),(1,0),(0,−1),(−1,0)] 分别表示右下左上 4 个方向。
同时用一个下标 di 表示当前方向，初始值为 0。

每次移动，相当于把行号增加 DIRS[di][0]，把列号增加 DIRS[di][1]。

向右转 90°，相当于把 di 增加 1，但在 di=3 时要回到 di=0。两种情况合二为一，把 di 更新为 (di+1)mod4。

5. 参考代码

class Solution {
    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上

    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> ans = new ArrayList<>(m * n); // 预分配空间
        int i = 0;
        int j = 0;
        int di = 0;
        for (int k = 0; k < m * n; k++) { // 一共走 mn 步
            ans.add(matrix[i][j]);
            matrix[i][j] = Integer.MAX_VALUE; // 标记，表示已经访问过（已经加入答案）
            int x = i + DIRS[di][0];
            int y = j + DIRS[di][1]; // 下一步的位置
            // 如果 (x, y) 出界或者已经访问过
            if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == Integer.MAX_VALUE) {
                di = (di + 1) % 4; // 右转 90°
            }
            i += DIRS[di][0];
            j += DIRS[di][1]; // 走一步
        }
        return ans;
    }
}

原文地址：https://blog.csdn.net/apple_74262176/article/details/143410540

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