Java教程

剑指Offer 29. 顺时针打印矩阵

本文主要是介绍剑指Offer 29. 顺时针打印矩阵,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述:
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 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]

方法一:
image-20210703201136291
按顺时针的方向,从外到里打印矩阵的值。下图的矩阵打印结果为:1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10。一层一层从外到里打印,观察可知每一层打印都有相同的处理步骤,唯一不同的是上下左右的边界不同了。因此使用四个变量 r1, r2, c1, c2 分别存储上下左右边界值,从而定义当前最外层。打印当前最外层的顺序:从左到右打印最上一行 —> 从上到下打印最右一行 —> 从右到左打印最下一行 —> 从下到上打印最左一行。应当注意只有在 r1 < r2(超过两行) 时才打印最下一行,也就是在当前最外层的行数大于 1 时才打印最下一行,这是因为当前最外层只有一行时,继续打印最下一行,会导致重复打印。打印最左一行也要做同样处理。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        if (matrix == null) {
            return null;
        }
        if (matrix.length == 0) {
            return list;
        }
        int r1 = 0; // 上边界
        int r2 = matrix.length - 1; // 下边界,注意需要减1
        int c1 = 0; // 左边界
        int c2 = matrix[0].length - 1; // 右边界,注意需要减1
        while (r1 <= r2 && c1 <= c2) {
            // 上方
            for (int i = c1; i <= c2; i++) {
                list.add(matrix[r1][i]);
            }
            // 右方
            for (int i = r1 + 1; i <= r2; i++) {
                list.add(matrix[i][c2]);
            }
            // 超过两行时才进行下方遍历
            if (r1 < r2) {
                for (int i = c2 - 1; i >= c1; i--) {
                    list.add(matrix[r2][i]);
                }
            }
            // 超过两列时才进行左方遍历
            if (c1 < c2) {
                for (int i = r2 - 1; i > r1; i--) {
                    list.add(matrix[i][c1]);
                }
            }
            // 遍历完成一个圈,更新边界,继续遍历内圈
            r1++; r2--; c1++; c2--;
        }
        return list;
    }
}

时间复杂度:因为要遍历每个矩阵的每个元素,所以为 O ( m + n ) O(m+n) O(m+n),空间复杂度:上述代码中虽然新建一个列表暂存矩阵的元素,但是对于算法的实现,并不需要开辟额外的空间,所以空间复杂度为 O ( 1 ) O(1) O(1)。
最后还需要注意一点:本题在力扣上函数的返回值是int[ ],而在牛客网上函数的返回值是ArrayList,所以在力扣上遍历矩阵元素后,按照下面来处理:首先新建一个数组arr,长度是m*n,数组下标index初始化为0,之后每遍历到一个元素,arr[index++] = 每次遍历到的元素。其他核心代码都相同。


结束语:如果本篇博客对您有帮助,请点赞、收藏或关注,您的鼓励是博主进步的动力,感谢支持,共同进步。

这篇关于剑指Offer 29. 顺时针打印矩阵的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!