题目

• 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

实现

Java实现

思路： 思考顺时针螺旋顺序什么时候需要变换方向，第一种情况：在遍历的时候角标越界，第二种情况：要访问的元素已经被访问过了，这两种情况下需要转动方向，首先我们确定两个方向数组，一个是x变动的方向，顺时针方向x的移动为向右、向下、向左、向上，对应变化为不变，+1，不变，-1，y变动的方向为+1，不变，-1，不变，在遍历完一个元素之后我们用0作为标记

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        //什么时候需要改变方向
        //1.角标越界时
        //2.在之前这个元素已经被访问过：使用0作为标记
        List<Integer> res = new ArrayList<>();
        //定义方向数组，顺指针旋转方向为右下左上
        //对于x则为不变，+1，不变，-1
        //对于y则为+1,不变，-1，不变
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        //矩阵的行数
        int m = matrix.length;
        //矩阵的列数
        int n = matrix[0].length;
        //x,y为坐标，d为方向
        int x = 0, y = 0, d = 0;
        for (int k = 0; k < m * n; k++) {
            res.add(matrix[x][y]);
            //表示已经访问过
            matrix[x][y] = 0;
            int i = x + dx[d];
            int j = y + dy[d];
            //角标越界或已经访问过，则改变方向
            if (i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] == 0) {
                d = (d + 1) % 4;
                i = x + dx[d];
                j = y + dy[d];
            }
            x = i;
            y = j;
        }
        return res;
    }
}

• 时间复杂度：O(mn)
• 空间复杂度：O(1)