题目地址(29. 顺时针打印矩阵)

https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
同螺旋矩阵

题目描述

  1. 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
  5. 示例 1：
  7. 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
  8. 输出：[1,2,3,6,9,8,7,4,5]
  11. 示例 2：
  13. 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
  14. 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
  19. 限制：
  21. 0 <= matrix.length <= 100
  22. 0 <= matrix[i].length <= 100
  24. 注意：本题与主站 54 题相同：https://leetcode-cn.com/problems/spiral-matrix/

前置知识


公司

  • 暂无

思路

image.png
我采用的是不遍历到底的方法 定义好左右上下边界 每遍历一层 就往里缩一圈 直到剩下最后一行或一列 再单独处理

关键点

  • 矩阵不一定是方阵

top < bottom && left < right 是循环的条件
无法构成“环”了，就退出循环，退出时可能是这 3 种情况之一：
top == bottom && left < right —— 剩一行
top < bottom && left == right —— 剩一列
top == bottom && left == right —— 剩一项（也算 一行/列）

代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.     public int[] spiralOrder(int[][] matrix) {
  4.         //如果矩阵为空 返回空
  5.         if (matrix.length == 0) return new int[0];
  6.         //数组大小为矩阵长乘宽
  7.         int[] res = new int[matrix.length * matrix[0].length];
  8.         //定义边界
  9.         int zuo = 0;
  10.         int you = matrix[0].length-1;
  11.         int shang = 0;
  12.         int xia = matrix.length-1;
  13.         //res每次插入的下标
  14.         int index =0 ;
  15.         //左右上下都满足的情况 继续循环 有一边不满足继续下面的判断
  16.         while (zuo < you && shang < xia) {
  17.             //依次是左到右 上到下 右到左 下到上
  18.             for (int i = zuo; i <you ; i++) res[index++] = matrix[shang][i];
  19.             for (int i = shang; i < xia ; i++) res[index++] = matrix[i][you];
  20.             for (int i = you; i > zuo ; i--) res[index++] = matrix[xia][i];
  21.             for (int i = xia; i > shang ; i--)  res[index++] = matrix[i][zuo];
  22.             //矩阵向内缩一层
  23.             zuo++;
  24.             you--;
  25.             shang++;
  26.             xia--;
  27.         }
  28.         //剩下的是一列 从上到下加入数组
  29.         if (zuo == you) {
  30.             for (int i = shang; i <=xia ; i++) {
  31.                 res[index++] = matrix[i][you];
  32.             } 
  33.         }//剩下的是一行 一定是else if
  34.          else if (shang == xia) {
  35.             for (int i = zuo; i <=you ; i++) {
  36.                 res[index++] = matrix[shang][i];
  37.             }
  38.         }
  39.         return res;
  40.     }
  41. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：剑指 Offer 29. 顺时针打印矩阵 - 图2#card=math&code=O%28n%29&id=geve5)
  • 空间复杂度：剑指 Offer 29. 顺时针打印矩阵 - 图3#card=math&code=O%28n%29&id=KBiR3)