【Leetcode Top 100】54. 螺旋矩阵

问题背景

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

数据约束

• $m==matrix.length$
• $n==matrix[i].length$
• $1\le m,n\le 10$
• $-100\le matrix[i][j]\le 100$

解题过程

按顺序定义方向，试探下一步的位置，即时修正遍历的方向即可。
这样的做法有两个问题：

• 遍历的过程中需要标记矩阵中哪些元素已经访问过，否则没有办法处理不越界但需要调整方向的情况。这样一来就完全更改了原数组中的元素，这是不符合遍历的初衷的。
• 如果数组中的数据类型包含数据类型可表示的所有数，这个标记并不是很好找，也许需要额外定义标记数组。

每一次方向变化之后，$m$ 与 $n$ 的修改是有规律的。可以先移动指针，等当前轮遍历结束之后，将 $n$ 修改为 $m-1$ 并将 $m$ 修改为 $n$ 来实现螺旋遍历。

上述两种做法的时空复杂度是一样的，第二种方法更进一步地利用了规律，所以可以规避免第一种方法的一些弊端。

具体实现

标记数组

class Solution {

    private static final int[][] DIRECTIONS = {{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> res = new ArrayList<>();
        int i = 0, j = 0, dirction = 0;
        for(int k = 0; k < m * n; k++) {
            res.add(matrix[i][j]);
            matrix[i][j] = Integer.MAX_VALUE;
            // 试探下一步的元素
            int x = i + DIRECTIONS[dirction][0];
            int y = j + DIRECTIONS[dirction][1];
            // 下一步坐标越界或者相应已经被遍历过，更改方向
            if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == Integer.MAX_VALUE) {
                dirction = (dirction + 1) % 4;
            }
            // 移动指针
            i += DIRECTIONS[dirction][0];
            j += DIRECTIONS[dirction][1];
        }
        return res;
    }
}

修改行列

class Solution {

    private static final int[][] DIRECTIONS = {{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> res = new ArrayList<>();
        int i = 0, j = -1, size = m * n;
        // 外层循环迭代地修改方向，结束条件是结果集中包含矩阵中的全部元素
        for(int dirction = 0; res.size() < size; dirction = (dirction + 1) % 4) {
            // 内层循环负责当前轮的遍历，移动指针记录增加答案
            for(int k = 0; k < n; k++) {
                i += DIRECTIONS[dirction][0];
                j += DIRECTIONS[dirction][1];
                res.add(matrix[i][j]);
            }
            // 修改 n 和 m 的值
            int temp = n;
            n = m - 1;
            m = temp;
        }
        return res;
    }
}

原文地址：https://blog.csdn.net/2401_88859777/article/details/143960501

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