[每日一题] 第二十一题:顺时针打印矩阵

题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

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

限制:

0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

题解

方法一:模拟、设定边界

解题思路

根据题目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的对应输出 [1,2,3,6,9,8,7,4,5]可以发现,顺时针打印矩阵的顺序是“从左向右,从上到下,从右向左,从下向上”循环。

  • 因此,考虑设定矩阵的“左,上,右,下”四个便捷,模拟以上矩阵遍历顺序。

[每日一题] 第二十一题:顺时针打印矩阵

算法流程

  1. 空值处理:matrix 为空时,直接返回空列表 [] 即可。

  2. 初始化: 矩阵 左、右、上、下 四个边界 lrtb,用于打印的结果列表 res

  3. 循环打印: “从左向右,从上向下,从右向左,从下向上”四个方向循环,每个方向打印中做以下三件事(各方向的具体信息见下表):

    1. 根据边界打印,即将元素按顺序添加至列表 res 尾部;
    2. 边界向内收缩 1(代表已被打印);
    3. 判断是否打印完毕(边界是否相遇),若打印完毕则跳出。
  4. 返回值: 返回 res 即可。

打印方向 1. 根据边界打印 2. 边界向内收缩 3. 是否打印完毕
从左向右 左边界l ,右边界 r 上边界 t 加 11 是否 t > b
从上向下 上边界 t ,下边界b 右边界 r 减 11 是否 l > r
从右向左 右边界 r ,左边界l 下边界 b 减 11 是否 t > b
从下向上 下边界 b ,上边界t 左边界 l 加 11 是否 l > r

复杂度分析:

时间复杂度 O(MN) : M, N 分别为矩阵行数和列数。
空间复杂度 O(1): 四个边界 lrtb 使用常数大小的 额外 空间(res 为必须使用的空间)。

代码

Java 代码利用了 ++ 操作的便利性

  • res[x++] 等价于先给 res[x] 赋值,再给 x 自增 1;
  • ++t > b 等价于先给 t 自增 1,再判断 t > b 逻辑表达式。
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
        int[] res = new int[(r + 1) * (b + 1)];
        while(true) {
            for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right.
            if(++t > b) break;
            for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom.
            if(l > --r) break;
            for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left.
            if(t > --b) break;
            for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top.
            if(++l > r) break;
        }
        return res;
    }
}

个人理解

  1. 规律: 该解法有一个规律,就是顺时针打印对应的是一个循环,这个循环就是从左到右,从上到下,从右到左,从下到上,通过该循环可以解决方向的问题,我们不必再控制方向如何变,我们只需要一个 while 循环,在条件满足的情况下,依次执行上述各个方向遍历,就是方向的控制。
  2. 边界设置: left=0right=matrix[0].lengthtop=0bottom=matrix.length
  3. 需要定义一个返回结果数组 result[],同时还需要定义一个索引下标,用来向数组中写数据使用,即 index=0
  4. 循环赋值: 我们应该怎样循环赋值呢,以从左向右为例,我们需要找到左边界和右边界,即 leftright,从左向右依次遍历即可,那么我们怎么确定是数组中的哪个值呢?我们还需要知道我们位于哪一行,这时候就需要 top 参数了,通过 matrix[top][i] 我们就可以知道这是数据中的哪个值了。
  5. 判断什么边界: 当我们按照一个方向循环遍历完事之后,我们应该如何判断边界,判断什么边界呢?以从左向右 为例,该方向遍历完成之后,我们下一个方向应该是从上到下,所以我们应该判断从上到下的边界是否超过。
  6. 如何比较边界:从左向右为例,我们应该比较上下边界了,那么怎样才算超出边界呢,top=bottom ?当 top=bottom 时说明此时应该为最后遍历的一行,所以应该 top>bottom的时候超出边界了。
  7. 二维数组下标: 在这个过程中一定不弄反了坐标,topbottom横坐标leftright纵坐标

以下代码是按照自我理解写的,简化后就是上述代码:

class Solution {
    public int[] spiralOrder(int[][] matrix) {

        if (matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int left = 0;
        int right = matrix[0].length - 1;
        int top = 0;
        int bottom = matrix.length - 1;
        int length = matrix.length*matrix[0].length;
        int[] result = new int[length];
        int index = 0;

        while (true) {
            //从左向右
            for (int i=left; i<=right; i++) {
                result[index] = matrix[top][i];
                index++;
            }
            top++;
            if (top > bottom) {
                break;
            }
            //从上到下
            for (int i=top; i<=bottom; i++) {
                result[index] = matrix[i][right];
                index++;
            }
            right--;
            if(left > right) {
                break;
            }
            //从右到左
            for (int i=right; i>=left; i--) {
                result[index] = matrix[bottom][i];
                index++;
            }
            bottom--;
            if(top > bottom) {
                break;
            }
            //从下到上
            for( int i=bottom; i>=top; i--) {
                result[index] = matrix[i][left];
                index++;
            }
            left++;
            if (left > right) {
                break;
            }

        }

        return result;
    }
}

来源

作者:jyd
链接:leetcode-cn.com/problems/shun-shi-...
来源:力扣(LeetCode)

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!