LeetCode.054.Spiral Matrix 螺旋矩阵

题目描述

54 Spiral Matrix
https://leetcode-cn.com/problems/spiral-matrix/

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

---

相似题目

LeetCode.054.Spiral Matrix 螺旋矩阵
LeetCode.剑指offer.029.顺时针打印矩阵

---

解题过程

顺时针螺旋打印二维数组，快看漫画 一面的时候让写过这道题，当时第一次写也写出来了。

用圈数做循环控制

模拟顺时针打印过程，从从外层开始一圈一圈的往内层遍历，先计算出圈数，用圈数做循环控制

需要注意的点：
1、遍历每一圈时，先计算出上、下、左、右边界会极大方便后续的遍历，然后依次遍历上、右、下、左。
2、由于并不是方阵，所以遍历的圈数是 (min(length, width) + 1)/2，其中的加 1 是为了兼容长和宽的最小值是奇数的情况，比如长宽都是 3 则遍历的圈数应该是 2。
3、当长和宽不同时，每一圈的遍历过程中，下边可能是上边已经遍历过的，左边可能是右边已经遍历过的，比如 1 × 2 的矩阵，只需遍历一圈，但第一圈的下边其实已经被上边遍历过了。再比如 2 × 1 的矩阵，左边已经被右边遍历过了，此时需要特殊判断一下。
4、注意二维数组的判空，要判断 matrix 不是 null，matrix 的长度不是 0 即不是 {}， matrix[0] 的长度不是 0 即不是 { {} }

时间复杂度 O(mn)，空间复杂度 O(1)，返回列表不算入空间复杂度

private static class SolutionV202006 {
    public List<Integer> spiralOrder(int[][] matrix) {
        if (null == matrix || matrix.length < 1 || matrix[0].length < 1) {
            return Collections.emptyList();
        }
        int rows = matrix.length, columns = matrix[0].length;

        // 要遍历的圈数
        int circles = (Math.min(matrix.length, matrix[0].length) + 1) / 2;

        List<Integer> res = new ArrayList<>();
        for (int k = 0; k < circles; k++) {
            // 先确定上、下、左、右四个边界值，之后就好遍历了
            int left = k, right = columns - 1 - k, up = k, down = rows - 1 - k;
            // 上
            for (int j = left; j <= right; j++) {
                res.add(matrix[up][j]);
            }
            // 右
            for (int i = up + 1; i <= down; i++) {
                res.add(matrix[i][right]);
            }
            // 下，down == up 时表示是单行数据，如果下面再横着遍历一次就重复了
            for (int j = right - 1; j >= left && down > up; j--) {
                res.add(matrix[down][j]);
            }
            // 左，left == right 时表示是单列数据，如果左侧再遍历一次就重复了
            for (int i = down - 1; i >= up + 1 && left < right; i--) {
                res.add(matrix[i][left]);
            }
        }
        return res;
    }
}

用上下左右边界做循环控制

我的方法是计算出圈数，用圈数做循环控制。看官方题解是用四个变量 left, right, top, bottom 做循环控制，好像更方便，循环条件是 while (top <= bottom && left <= right)，每次循环完后只需对这四个变量进行加减1操作即可。

---

GitHub代码

algorithms/leetcode/leetcode/_054_SpiralMatrix.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_054_SpiralMatrix.java

---