LeetCode 热题 100_螺旋矩阵（19_54_中等_C++）（按层模拟）

题目描述：

给你一个 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

题解：

解题思路：

思路一（按层模拟）：
1、通过给的示例，我们可以联想到切方块豆腐的场景，按顺时针方向，从外向内先横着切一刀后竖着切一刀重复进行下去。这样我们的豆腐会越来越小，直到不能再切。

2、具体思路如下：
① 我们可以使用row_begin和row_end代表第一行和最后一行，使用column_begin和column_end代表第一列和最后一列。
② 这样我们可以根据豆腐的具体尺寸来控制豆腐的切块，注意row_begin=row_end时单看行方向是可以切一刀的，同理column_begin=column_end时也可以切一刀
③ 因为是按放行顺时针方向切豆腐，总共切了豆腐的四个方向（上右下左），所以我们可以分为四种切法。
④

3、复杂度分析
① 时间复杂度：O(NM),M代表行数，N代表列数，因只遍历一遍二维数组 。
② 空间复杂度：O(1),除了输出数组以外，空间复杂度是常数。

代码实现（思路一（按层模拟））：

#include<iostream>
#include<vector>
using namespace std;

vector<int> spiralOrder(vector<vector<int>>& matrix) {
	vector<int> ans;
	//用于区分四种情况 
	int n=1; 
	 
	int row_begin=0,row_end=matrix.size()-1; 
	int column_begin=0,column_end=matrix[0].size()-1;
	//注意row_end=row_begin或column_end=column_begin可以切 
	while(row_end>=row_begin&&column_end>=column_begin){
		//上_横着切_行的开始增大 
		if(n%4==1){
			for(int i=column_begin;i<=column_end;i++){
				ans.emplace_back(matrix[row_begin][i]);
			}
			++row_begin; 
		//右_竖着切_列的末尾减小 
		}else if(n%4==2){
			for(int i=row_begin;i<=row_end;i++){
				ans.emplace_back(matrix[i][column_end]);
			}
			--column_end;
		//下_横着切_行的末尾减小
		}else if(n%4==3){
			for(int i=column_end;i>=column_begin;i--){
				ans.emplace_back(matrix[row_end][i]);
			}
			--row_end;
		//左_竖着切_列的开始增大 
		}else{
			for(int i=row_end;i>=row_begin;i--){
				ans.emplace_back(matrix[i][column_begin]);
			}
			++column_begin;
		}
		++n;
	}
	return ans;
}

int main(){
	vector<vector<int>> matrix={{1,2,3,4},{5,6,7,8},{9,10,11,12}} ;
	
	vector<int> ans=spiralOrder(matrix);
	for(const auto i:ans){
		cout<<i<<" ";
	}
	return 0;
}

LeetCode 热题 100_螺旋矩阵（19_54)原题链接
欢迎大家和我沟通交流(✿◠‿◠)