019螺旋矩阵

螺旋矩阵题目链接https://leetcode.cn/problems/spiral-matrix/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public ListInteger spiralOrder(int[][] matrix) { int mmatrix.length, nmatrix[0].length; int up0, downm-1, left0, rightn-1; int i; int cnt0, countm*n; ListInteger ans new ArrayList(); while(cntcount){ for(ileft; irightcntcount; i){ ans.add(matrix[up][i]); cnt; } up; for(iup; idowncntcount; i){ ans.add(matrix[i][right]); cnt; } right--; for(iright; ileftcntcount; i--){ ans.add(matrix[down][i]); cnt; } down--; for(idown; iupcntcount; i--){ ans.add(matrix[i][left]); cnt; } left; } return ans; }分析代码的时间复杂度为O(m*n)空间复杂度为O(1)。解题思路模拟螺旋矩阵用up、right、down、left分别控制每次向上、右、下、左移动的边界每次移动后维护边界值的变化然后按顺序遍历矩阵即可。看了官方题解后的解答//方法一模拟 //时间复杂度O(mn) //空间复杂度O(mn) public ListInteger spiralOrder(int[][] matrix) { ListInteger ans new ArrayList(); if(matrixnull || matrix.length0 || matrix[0].length0){ return ans; } int m matrix.length, n matrix[0].length; int total m*n; int[][] directions new int[][]{{0,1},{1,0},{0,-1},{-1,0}}; boolean[][] flag new boolean[m][n]; int direction 0; int row0, column0; int newRow, newColumn; for(int i0; itotal; i){ ans.add(matrix[row][column]); flag[row][column]true; newRow rowdirections[direction][0]; newColumn columndirections[direction][1]; if(newRow0 || newRowm || newColumn0 || newColumnn || flag[newRow][newColumn]){ direction (direction1)%4;//一共四个移动方向下标从0-3 } row rowdirections[direction][0]; column columndirections[direction][1]; } return ans; } //方法二按层模拟 //时间复杂度O(mn) //空间复杂度O(1) public ListInteger spiralOrder(int[][] matrix) { ListInteger ans new ArrayList(); if(matrixnull || matrix.length0 || matrix[0].length0){ return ans; } int m matrix.length, n matrix[0].length; int top0, bottomm-1, left0, rightn-1; while(leftright topbottom){ //当前层从左往右遍历 for(int columnleft; columnright; column){ ans.add(matrix[top][column]); } //当前层从上往下遍历 for(int rowtop1; rowbottom; row){ ans.add(matrix[row][right]); } //矩阵还未遍历完成且当前层不仅只剩一行或者仅剩一列 if(leftright topbottom){ //当前层从右往左遍历 for(int columnright-1; columnleft; column--){ ans.add(matrix[bottom][column]); } //当前层从下往上遍历 for(int rowbottom-1; rowtop; row--){ ans.add(matrix[row][left]); } } top; bottom--; left; right--; } return ans; }分析​ 1、方法一的解题思路用一个二维数组direction维护移动方向按照向右、向下、向左、向上的顺序再用一个二维数组flag维护当前位置是否被访问过每次移动后若超出边界或者位置已经被访问过则需要跟新移动方向。​ 2、方法二的解题思路从最外层往开始遍历每次遍历一层遍历完后同时缩小上、下、左、右边界。注意当矩阵最后只剩一行未遍历时top等于bottom所以在进行从右向左和从下往上遍历前需要进行判断否则会重复遍历当矩阵最后只剩一列遍历时同理。总结本题主要需要模拟按从左往右、从上往下、从右往左、从下往上顺序遍历的过程。