LeetCode_螺旋遍历_中等_54.螺旋矩阵

骑猪看日落 2023-10-06 18:59 6阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

**示例 1：**

![在这里插入图片描述][3a00694099e04e4ca1b781c6467f3d57.png]  
输入：matrix = \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\]  
输出：\[1,2,3,6,9,8,7,4,5\]

**示例 2：**

![在这里插入图片描述][ba313d276dba463cafdc6ba675f8ecee.png]

输入：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\]

**提示：**  
m == matrix.length  
n == matrix\[i\].length  
1 <= m, n <= 10  
\-100 <= matrix\[i\]\[j\] <= 100

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/spiral-matrix

## 2.思路 ##

（1）螺旋遍历  
分析题目可知，按照顺时针螺旋顺序访问矩阵中的元素时，从起点 matrix\[0\]\[0\] 开始，总是按照**向右→向下→向左→向上**→向右→向下→…的方向开始遍历（**注意：若矩阵只有一列，则是按向下方向开始遍历**），直到将整个矩阵访问完为止。故可以考虑按照这个访问规律来返回矩阵中的所有元素，具体的步骤如下：

*  求出矩阵的行数和列数，即行数 m = matrix.length，列数 n = matrix\[0\].length。此外还需定义保存结果的 list 数组 res；
 *  为了防止在按上述方向访问时，重复遍历矩阵中的元素，所以可以设置一个与矩阵同行同列的 visited 数组，其元素类型为 boolean，若visited\[i\]\[j\] = true，则说明已经访问过矩阵中的元素matrix\[i\]\[j\]，否则说明没有访问；
 *  为了在程序中实现按上述方向访问，可以用 direction 来表示即将要遍历的方向，direction = 1、2、3、4分别表示在矩阵中向右、下、左、上遍历，值得注意的是**若矩阵只有一列，则是按向下方向开始遍历，故可设置 direction 的初始值为 (n == 1) ? 2 : 1**；
 *  设置起点坐标 i 和 j，在本题中，起点元素为 matrix\[0\]\[0\]，故其初始值均为0，然后再将起点添加到 res 中，以及设置 visited\[i\]\[j\]=true，即表示起点已经被访问过，以上准备工作完成后，便可以开始遍历了；
 *  在遍历过程中，使用 if-else 语句来判断遍历的方向，并且每访问到一个元素，就将该元素添加到 res 中，此外**在遍历过程中尤其要注意防止数组越界以及矩阵元素的重复访问**，当某一个元素的上述四个方向都不能访问时，则说明已经将矩阵的所有元素访问完成，此时直接退出循环并返回 res 即可。

（2）旋转遍历  
遍历当前 matrix 的第一行，然后**删除 matrix 的第一行，再将其逆时针旋转 90°**，然后继续遍历处理后的 matrix 的第一行，如此循环操作…，直到 matrix 的行数为 0 为止，这样一来便可以按照题目要求对矩阵进行螺旋遍历。

相关题目：  
[LeetCode\_螺旋遍历\_中等\_59.螺旋矩阵 II][LeetCode_59._ II]

## 3.代码实现（Java） ##

//思路1————螺旋遍历
    class Solution {
        
    	public List<Integer> spiralOrder(int[][] matrix) {
        
    	    //矩阵 matrix 是 m 行 n 列的
    	    int m = matrix.length;
    	    int n = matrix[0].length;
    	    //定义 res，用于保存结果
    	    List<Integer> res = new ArrayList<Integer>();
    	    //visited[i][j] == true 表示已经访问过矩阵中的元素 matrix[i][j]
    	    boolean[][] visited = new boolean[m][n];
    	    //direction = 1、2、3、4 时分别表示在矩阵中向右、下、左、上遍历
    		/*
    			初始时:
    			若 n == 1，则说明矩阵只有一列，此时只能向下开始遍历
    			若 n != 1，则说明矩阵有多列，此时可以按照向右→向下→向左→向上→向右→向下→...的方向开始遍历，直到将整个矩阵访问完为止
    		*/
    	    int direction = (n == 1) ? 2 : 1;
    	    //定义遍历起点的横纵坐标
    	    int i = 0, j = 0;
    	    //将遍历的起点 matrix[i][j] 添加到 res 中
    	    res.add(matrix[i][j]);
    	    //将遍历的起点设置为已访问的状态
    	    visited[i][j] = true;
    	    while (true) {
        
    	        if (direction == 1 && j + 1 < n && visited[i][j + 1] == false) {
        
    	            //向右遍历
    	            while (j + 1 < n && visited[i][j + 1] == false) {
        
    	                res.add(matrix[i][j + 1]);
    	                visited[i][j + 1] = true;
    	                j++;
    	            }
    	            direction++;
    	        } else if (direction == 2 && i + 1 < m && visited[i + 1][j] == false) {
        
    	            //向下遍历
    	            while (i + 1 < m && visited[i + 1][j] == false) {
        
    	                res.add(matrix[i + 1][j]);
    	                visited[i + 1][j] = true;
    	                i++;
    	            }
    	            direction++;
    	        } else if (direction == 3 && j - 1 >= 0 && visited[i][j - 1] == false) {
        
    	            //向左遍历
    	            while (j - 1 >= 0 && visited[i][j - 1] == false) {
        
    	                res.add(matrix[i][j - 1]);
    	                visited[i][j - 1] = true;
    	                j--;
    	            }
    	            direction++;
    	        } else if (direction == 4 && i - 1 >= 0 && visited[i - 1][j] == false) {
        
    	            //向上遍历
    	            while (i - 1 >= 0 && visited[i - 1][j] == false) {
        
    	                res.add(matrix[i - 1][j]);
    	                visited[i - 1][j] = true;
    	                i--;
    	            }
    	            direction = 1;
    	        } else {
        
    	            //遍历结束
    	            break;
    	        }
    	    }
    	    return res;
    	}
    }

//思路2————旋转遍历
    class Solution {
        
        public List<Integer> spiralOrder(int[][] matrix) {
        
            List<Integer> res = new ArrayList<>();
            while (matrix.length >= 1) {
        
                //遍历当前 matrix 的第一行
                for (int num : matrix[0]) {
        
                    res.add(num);
                }
                //删除 matrix 的第一行，再将其逆时针旋转 90° 后并返回
                matrix = DelRotateMatrix(matrix);
            }
            return res;
        }
    
        private int[][] DelRotateMatrix(int[][] matrix) {
        
            //每次处理列数不变
            int m = matrix[0].length;
            //每次处理行数少一行
            int n = matrix.length - 1;
            int[][] newMatrix = new int[m][n];
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    newMatrix[i][j] = matrix[j + 1][m - i - 1];
                }
            }
            return newMatrix;
        }
    }

[3a00694099e04e4ca1b781c6467f3d57.png]: https://img-blog.csdnimg.cn/3a00694099e04e4ca1b781c6467f3d57.png
[ba313d276dba463cafdc6ba675f8ecee.png]: https://img-blog.csdnimg.cn/ba313d276dba463cafdc6ba675f8ecee.png
[LeetCode_59._ II]: https://blog.csdn.net/weixin_43004044/article/details/119816911