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

019螺旋矩阵

news 2026/5/6 13:27:11

螺旋矩阵

题目链接：https://leetcode.cn/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

public List<Integer> spiralOrder(int[][] matrix) { int m=matrix.length, n=matrix[0].length; int up=0, down=m-1, left=0, right=n-1; int i; int cnt=0, count=m*n; List<Integer> ans = new ArrayList<>(); while(cnt<count){ for(i=left; i<=right&&cnt<count; i++){ ans.add(matrix[up][i]); cnt++; } up++; for(i=up; i<=down&&cnt<count; i++){ ans.add(matrix[i][right]); cnt++; } right--; for(i=right; i>=left&&cnt<count; i--){ ans.add(matrix[down][i]); cnt++; } down--; for(i=down; i>=up&&cnt<count; i--){ ans.add(matrix[i][left]); cnt++; } left++; } return ans; }

分析：代码的时间复杂度为O(m*n)，空间复杂度为O(1)。解题思路：模拟螺旋矩阵，用up、right、down、left分别控制每次向上、右、下、左移动的边界，每次移动后维护边界值的变化，然后按顺序遍历矩阵即可。

看了官方题解后的解答：

//方法一：模拟 //时间复杂度：O(mn) //空间复杂度：O(mn) public List<Integer> spiralOrder(int[][] matrix) { List<Integer> ans = new ArrayList<>(); if(matrix==null || matrix.length==0 || matrix[0].length==0){ 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 row=0, column=0; int newRow, newColumn; for(int i=0; i<total; i++){ ans.add(matrix[row][column]); flag[row][column]=true; newRow = row+directions[direction][0]; newColumn = column+directions[direction][1]; if(newRow<0 || newRow>=m || newColumn<0 || newColumn>=n || flag[newRow][newColumn]){ direction = (direction+1)%4;//一共四个移动方向，下标从0-3 } row = row+directions[direction][0]; column = column+directions[direction][1]; } return ans; } //方法二：按层模拟 //时间复杂度：O(mn) //空间复杂度：O(1) public List<Integer> spiralOrder(int[][] matrix) { List<Integer> ans = new ArrayList<>(); if(matrix==null || matrix.length==0 || matrix[0].length==0){ return ans; } int m = matrix.length, n = matrix[0].length; int top=0, bottom=m-1, left=0, right=n-1; while(left<=right && top<=bottom){ //当前层从左往右遍历 for(int column=left; column<=right; column++){ ans.add(matrix[top][column]); } //当前层从上往下遍历 for(int row=top+1; row<=bottom; row++){ ans.add(matrix[row][right]); } //矩阵还未遍历完成且当前层不仅只剩一行或者仅剩一列 if(left<right && top<bottom){ //当前层从右往左遍历 for(int column=right-1; column>=left; column--){ ans.add(matrix[bottom][column]); } //当前层从下往上遍历 for(int row=bottom-1; row>top; row--){ ans.add(matrix[row][left]); } } top++; bottom--; left++; right--; } return ans; }

分析：

1、方法一的解题思路：用一个二维数组direction维护移动方向，按照向右、向下、向左、向上的顺序，再用一个二维数组flag维护当前位置是否被访问过，每次移动后若超出边界或者位置已经被访问过，则需要跟新移动方向。

2、方法二的解题思路：从最外层往开始遍历，每次遍历一层，遍历完后同时缩小上、下、左、右边界。注意，当矩阵最后只剩一行未遍历时，top等于bottom，所以在进行从右向左和从下往上遍历前需要进行判断，否则会重复遍历；当矩阵最后只剩一列遍历时同理。