当前位置：首页 > news >正文

LeetCode100之螺旋矩阵(54)--Java

news 2024/11/14 23:30:01

1.问题描述

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

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

提示

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

难度等级

中等

题目链接

螺旋矩阵

2.解题思路

这道螺旋矩阵的题，说白了，就是按照顺时针绕圈进行遍历。我们可以将顺时针拆分为四个部分，从左到右、从上到下、从右到左和从下到上。

知道题目该怎么做之后，我们可以定义四个变量，分别用来表示该次遍历的首尾行索引和首尾列索引(借助这四个索引实现绕圈)，已经一个存储答案的List列表。

        //首行索引int startX = 0;//末尾行索引int endX = matrix.length-1;//首列索引int startY = 0;//末尾列索引int endY = matrix[0].length-1;//存储数据List<Integer> data = new ArrayList<>();

因为我们每次遍历，其实是在绕圈，直到绕到最里面为止，也就是最终只剩一行或者最终只剩一列，前面提到的两种情况同时发生的话，则是在一个m*m的矩阵中，最后剩下中间那一个数。所以我们可以用一个循环来实现不断向矩阵内部绕圈，循环可以不断进行的条件就是首行索引不超过末尾行索引(取 = 时矩阵最终只剩一行)和首列索引不超过末尾列索引(取=时矩阵最终只剩一列)。

      while(startX <= endX && startY <= endY)......

接着我们就可以开始顺时针遍历了。

根据题目要求，我们要先从左向右遍历，此时我们遍历的是未遍历过的那部分矩阵的首行，从首列一直遍历到末尾列。从左向右遍历结束后，我们要更新首行的索引，因为原来的首行已经被我们刚刚遍历过了。

        //从左到右for(int i = startY;i <= endY;i++){data.add(matrix[startX][i]);}//更新首行索引startX++;

接着，我们要从上到下遍历，此时我们遍历的是未遍历过的那部分矩阵的末尾列，从首行一直遍历到末尾行。从上到下遍历结束后，我们也要更新末尾列的索引，因为原来的末尾列已经被我们刚刚遍历过了。

        //从上到下for(int i = startX;i <= endX;i++){data.add(matrix[i][endY]);}//更新末尾列索引endY--;

然后，我们在这里还要做一个判断，因为首行与末尾列索引都改变了，我们此时要判断矩阵是否已经遍历完了，不是才要进行下面的遍历。

        //判断首行索引是否大于末尾行索引//判断首列索引是否大于末尾列索引if(startX > endX ||startY > endY){break;}

如果矩阵还没遍历完，我们就要继续从右到左遍历，此时我们遍历的是未遍历过的那部分矩阵的末尾行，从末尾列一直遍历到首列。从右向左遍历结束后，我们要更新末尾列的索引，因为原来的末尾列已经被我们刚刚遍历过了。

        //从右到左for(int i = endY;i >= startY;i--){data.add(matrix[endX][i]);}//更新末尾行索引endX--;

接着，我们要从下到上遍历，此时我们遍历的是未遍历过的那部分矩阵的首列，从末尾行一直遍历到首行。从下到上遍历结束之后，我们也要更新首列的索引，因为原来的首列已经被我们刚刚遍历过了。

        //从下到上for(int i = endX;i >= startX;i--){data.add(matrix[i][startY]);}//更新首列索引startY++;

重复上述操作，直到整个矩阵被遍历完全。

最后将存储答案的List集合返回即可。

     //返回结果return data;

3.代码展示

class Solution {public List<Integer> spiralOrder(int[][] matrix) {//首行索引int startX = 0;//末尾行索引int endX = matrix.length-1;//首列索引int startY = 0;//末尾列索引int endY = matrix[0].length-1;//存储数据List<Integer> data = new ArrayList<>();while(startX <= endX && startY <= endY){//从左到右for(int i = startY;i <= endY;i++){data.add(matrix[startX][i]);}//更新首行索引startX++;//从上到下for(int i = startX;i <= endX;i++){data.add(matrix[i][endY]);}//更新末尾列索引endY--;//判断首行索引是否大于末尾行索引//判断首列索引是否大于末尾列索引if(startX > endX ||startY > endY){break;}//从右到左for(int i = endY;i >= startY;i--){data.add(matrix[endX][i]);}//更新末尾行索引endX--;//从下到上for(int i = endX;i >= startX;i--){data.add(matrix[i][startY]);}//更新首列索引startY++;}//返回结果return data;}
}