【LC100】No54. 螺旋矩阵

题目描述

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

提示:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 10

• -100 <= matrix[i][j] <= 100

示例

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

链接

思路

总有一种上学的时候曾经做过的感觉。

解法一：模拟螺旋路径

设置四个变量分别表示：上方第一行 top，下方最后一行 bottom，左边第一列 left，右边最后一列 right。

然后模拟螺旋的路径，每当循环完一次，就让对应行或列消失，直到最中心元素。

代码

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return list;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = n - 1, top = 0, bottom = m - 1;
        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++) {
                list.add(matrix[top][i]);
            }
            top++;
            for (int i = top; i <= bottom; i++) {
                list.add(matrix[i][right]);
            }
            right--;
            // 螺旋到下方
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    list.add(matrix[bottom][i]);
                }
                bottom--;
            }
            // 螺旋到左边
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    list.add(matrix[i][left]);
                }
                left++;
            }
        }
        return list;
    }
}

• 时间复杂度：O(mn)

• 空间复杂度：O(mn)

解法二：方向数组，求模转弯

非常巧妙的一个方法。

螺旋其实是一个循环：向右，向下，向左，向上。我们可以使用一个方向数组来表示下标的变化。

例如，向右，是行下标不变，列下标 +1；向下，是行下标 +1，列下标不变。

因此，我们设置 int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}，代表四个方向。

从 (0, 0) 开始走，一开始向右取 DIRS[0]，之后向下取 DIRS[1]，以此类推。

代码中的 di 为方向数组的索引标识，di 的取值为 0, 1, 2, 3，很像是对 4 取模后的余数，我们要找下一个方向，所以是 di + 1 后再对 4 取模， di = (di + 1) % 4;

代码

class Solution {

    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public List<Integer> spiralOrder(int[][] matrix) {

        List<Integer> list = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return list;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0, j = 0;
        int di = 0;
        // k代表走的步数，最多是m*n步
        for (int k = 0; k < m * n; k++) {
            // 加入当前元素
            list.add(matrix[i][j]);
            matrix[i][j] = Integer.MAX_VALUE;  
            // 判断下一个元素是否越界
            int x = i + DIRS[di][0];
            int y = j + DIRS[di][1];
            if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == Integer.MAX_VALUE) {
                di = (di + 1) % 4;
            }
            // 找到下一个元素
            i += DIRS[di][0];
            j += DIRS[di][1];
        }
        return list;
    }
}

• 时间复杂度：O(mn)

• 空间复杂度：O(1)