当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.054.Spiral Matrix 螺旋矩阵

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 不是 nullmatrix 的长度不是 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


上一篇 LeetCode.128.Longest Consecutive Sequence 最长连续序列

下一篇 LeetCode.剑指offer.029.顺时针打印矩阵

阅读
评论
797
阅读预计3分钟
创建日期 2020-06-05
修改日期 2020-06-05
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论