- 设计思想:
-视频讲解链接B站视频讲解
- 复杂度分析:
- 代码:
c++版本:
class Solution { public: vector<int> spiralOrder(vector<vector<int> > &matrix) { int dir[4][2] = {{0,1}, {1,0},{0,-1},{-1,0}};//右下左上 vector<int> res; int m = matrix.size(); if(m == 0) return res; int n = matrix[0].size(); int x = 0,y = 0;//左上角,即为起点 int d = 0;//控制方向位 for(int i = 0;i < m * n;i ++){ res.push_back(matrix[x][y]); matrix[x][y] = INT_MAX;//遍历完就初始化很大的值 int dx = x + dir[d][0], dy = y + dir[d][1];//下一步要到达的位置 if(dx < 0 || dx >= m || dy < 0 || dy >= n || matrix[dx][dy] == INT_MAX){ //如果下一步溢出或者已经访问,就转换方向 d = (d + 1) % 4;///转变方向 //移动到下一个点 dx = x + dir[d][0]; dy = y + dir[d][1]; } x = dx; y = dy; } return res; } };
Java版本:
import java.util.*; public class Solution { public ArrayList<Integer> spiralOrder(int[][] matrix) { ArrayList<Integer> res = new ArrayList<>(); if(matrix.length==0) return res; int m = matrix.length, n = matrix[0].length; int x = 0,y = 0;//左上角,即为起点 int [][]dir = new int[][]{{0,1}, {1,0},{0,-1},{-1,0}};//右下左上 int d = 0;//控制方向位 for(int i = 0;i < m * n;i ++){ res.add(matrix[x][y]); matrix[x][y] = Integer.MAX_VALUE;//遍历完就初始化很大的值 int dx = x + dir[d][0], dy = y + dir[d][1];//下一步要到达的位置 if(dx < 0 || dx >= m || dy < 0 || dy >= n || matrix[dx][dy] == Integer.MAX_VALUE){ //如果下一步溢出或者已经访问,就转换方向 d = (d + 1) % 4;///转变方向 //移动到下一个点 dx = x + dir[d][0]; dy = y + dir[d][1]; } x = dx; y = dy; } return res; } }
Python版本:
# # # @param matrix int整型二维数组 # @return int整型一维数组 # class Solution: def spiralOrder(self , matrix ): # write code here res = [] if len(matrix) == 0: return res m,n = len(matrix),len(matrix[0]) x,y = 0,0#左上角,即为起点 dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]#右下左上 d = 0#控制方向位 for i in range(m * n): res.append(matrix[x][y]); matrix[x][y] = 2147483647#遍历完就初始化很大的值 dx,dy = x + dir[d][0],y + dir[d][1]#下一步要到达的位置 if dx < 0 or dx >= m or dy < 0 or dy >= n or matrix[dx][dy] == 2147483647: #如果下一步溢出或者已经访问,就转换方向 d = (d + 1) % 4#转变方向 #移动到下一个点 dx = x + dir[d][0] dy = y + dir[d][1] x = dx y = dy return res
JavaScript版本:
/** * * @param matrix int整型二维数组 * @return int整型一维数组 */ function spiralOrder( matrix ) { // write code here let res = []; if(matrix.length==0) return res; let m = matrix.length, n = matrix[0].length; let x = 0,y = 0;//左上角,即为起点 const dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];//右下左上 let d = 0;//控制方向位 for(let i = 0;i < m * n;i ++){ res.push(matrix[x][y]); matrix[x][y] = 2147483647;//遍历完就初始化很大的值 let dx = x + dir[d][0], dy = y + dir[d][1];//下一步要到达的位置 if(dx < 0 || dx >= m || dy < 0 || dy >= n || matrix[dx][dy] == 2147483647){ //如果下一步溢出或者已经访问,就转换方向 d = (d + 1) % 4;///转变方向 //移动到下一个点 dx = x + dir[d][0]; dy = y + dir[d][1]; } x = dx; y = dy; } return res; } module.exports = { spiralOrder : spiralOrder };