题意概述

• 给定一个m*n的矩阵
• 要求按照螺旋的顺序返回矩阵中的所有元素

方法一：方向数组转向

思路与具体做法

• 用一个方向数组d来进行矩阵遍历过程中的转向
• 当遍历过程中超过边界或遍历到已访问元素时就改变方向，具体做法是先按原来遍历方向尝试着进行遍历，若出矩阵范围或已访问，说明应该转向
• 每次转向按照右->下->左->上->右的顺序进行选择，用标记变量flag进行标记，每次转向中自增然后对四取余即实现对这个四个方向的闭环选择

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int>ans;
        int m=matrix.size(),n=matrix[0].size();//矩阵的大小 
        if(m==0)return ans;//空螺旋矩阵直接返回 
		int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//右下左上   
		int x=0,y=0,flag=0;//x,y数组下标，flag标记转向   
		for(int i=0;i<m*n;i++){
			ans.push_back(matrix[x][y]);
			matrix[x][y]=INT_MAX;//标记已访问 
			int newx=x+d[flag][0],newy=y+d[flag][1];//尝试到下一位置 
			if(newx<0||newx>=m||newy<0||newy>=n||matrix[newx][newy]==INT_MAX)flag=(++flag)%4;//该位置超出矩阵范围或已访问，说明应该转向 
			x+=d[flag][0],y+=d[flag][1];//到达正确的下一位置 
		} 
		return ans;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(m\ast n)O(m*n)$O(m∗n)，遍历了整个二维数组
• 空间复杂度：$O(m\ast n)O(m*n)$O(m∗n)，遍历结果数组ans共m*n个元素

方法二：模拟

思路与具体做法

• 模拟螺旋矩阵的路径。
• 初始位置是矩阵左上角，两层循环，外层循环在遍历元素<=全部元素的时候就继续遍历，内层循环，设立四个循环分别从右->下->左->上四个方向不断枚举
• 外层循环走一遍具体表现是螺旋矩阵绕一圈，每次令层数加一

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int>ans;
        int m=matrix.size(),n=matrix[0].size();//矩阵的大小 
        if(m==0)return ans;//空螺旋矩阵直接返回 
        int cn=0,layer=0;//cn用于计数，layer记录螺旋矩阵的层数 
		while(cn<m*n){
			for(int i=layer;i<n-layer;i++){//向右，初始从[0][0~n-1] 
				ans.push_back(matrix[layer][i]);cn++;
			}
            if(cn>=m*n)break;
			for(int i=layer+1;i<m-layer;i++){//向下，初始从[1~m-1][n-1] 
				ans.push_back(matrix[i][n-1-layer]);cn++;
			}
            if(cn>=m*n)break;
			for(int i=n-2-layer;i>=layer;i--){//向左，初始从[m-1][n-2~0] 
				ans.push_back(matrix[m-1-layer][i]);cn++;
			}
			for(int i=m-2-layer;i>layer;i--){//向上，初始从[m-2~1][0] 
				ans.push_back(matrix[i][layer]);cn++;
			}
			layer++;//层数加1			
		} 
		return ans;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(m\ast n)O(m*n)$O(m∗n)，遍历了整个二维数组
• 空间复杂度：$O(m\ast n)O(m*n)$O(m∗n)，遍历结果数组ans共m*n个元素