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

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

文章目录

• 【LeetCode】剑指 Offer 29. 顺时针打印矩阵
• 一、设定边界
• 二、按层模拟
• 总结

一、设定边界

根据题目示例可以发现，顺时针打印矩阵的顺序是”从左向右，从上向下、从右向左、从下向上“循环

因此，考虑设定矩阵的”左、上、右、下“四个边界，模拟以上矩阵遍历顺序

算法流程：

• 空值处理：当 matrix 为空时，直接返回列表 [] 即可
• 初始化：矩阵左右上下四个边界 l、r、t、b，用于打印的结果列表 res
• 循环打印：”从左向右、从上向下、从右向左、从下向上“四个方向循环，每个方向打印中做以下三件事（各方向的具体信息见下表）；
  1. 根据边界打印，也就是将元素按顺序添加至列表 res 尾部
  2. 边界向内收缩 1 （代表已被打印）
  3. 判断是否打印完毕（边界是否相遇），若打印完毕则跳出
• 返回值：返回 res 即可
  

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
		int l = 0;
		int r = matrix[0].length - 1;
		int t = 0;
		int b = matrix.length - 1;
		int x = 0;
		int[] arr = new int[(r+1)*(b+1)];
        while(true) {
            for(int i = l; i <= r; i++) arr[x++] = matrix[t][i];
            if(++t > b) break;
            for(int i = t; i <= b; i++) arr[x++] = matrix[i][r];
            if(--r < l) break;
            for(int i = r; i >= l; i--) arr[x++] = matrix[b][i];
            if(--b < t) break;
            for(int i = b; i >= t; i--) arr[x++] = matrix[i][l];
            if(++l > r) break;
        }
        return arr;
    }
}			

• 时间复杂度 O(m*n)：M，N 分别为矩阵行数和列数
• 空间复杂度 P(1)：四个边界 l、r、t、b 使用常数大小的额外空间（res 为必须使用的空间）

二、按层模拟

可以将矩阵看成若干层，首先打印最外层的元素，其次打印次外层的元素，直到打印最内层的元素

定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如，下图矩阵最外层元素都是第 1 层，次外层元素都是第 2 层，剩下的元素都是第 3 层

[[1, 1, 1, 1, 1, 1, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 2, 3, 3, 3, 2, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 1, 1, 1, 1, 1, 1]]

对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于（top,left），右下角位于（bottom,right），按照如下顺序遍历当前层的元素

• 从左到右遍历上侧元素，依次为（top,left）到（top,right）
• 从上到下遍历右侧元素，依次为（top+1,right）到（bottom,right）
• 如果 left < right 且 top < bottom，则从右到左遍历下侧元素，依次为（bottom,right - 1）到（bottom,left + 1），以及从上到下遍历左侧元素，依次为（bottom,left）到（top + 1,left）

遍历完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续遍历，直到遍历完所有元素为止

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
        int rows = matrix.length;
        int columns = matrix[0].length;
        int[] arr = new int[columns * rows];
        int l = 0;
        int t = 0;
        int r = columns - 1;
        int b = rows - 1;
        int x = 0;
        while(l <= r && t <= b){
            for(int i = l; i <= r; i++){
                arr[x++] = matrix[t][i]; 
            }
            for(int i = t+1; i <= b; i++){
                arr[x++] = matrix[i][r];
            }
            //如果 l = r，或者 t = b，那就不需要执行下面了，只需要进行下一次 while 循环就能遍历完
            if(l < r && t < b){
                for(int i = r - 1; i > l; i--){
                    arr[x++] = matrix[b][i];
                }
                for(int i = b; i > t; i--){
                    arr[x++] = matrix[i][l];
                }
            }
            l++;
            t++;
            r--;
            b--;
        }
        return arr;
    }
}

• 时间复杂度：O(m * n)，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次
• 空间复杂度：O(1)，除了输出数组外，空间复杂度是常数

总结

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