LeetCode 面试经典 150_矩阵_螺旋矩阵（35_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 时也可以切一刀。
③ 因为是按顺时针方向切豆腐，总共切了豆腐的四个方向（上右下左），所以我们可以分为四种切法。
④ 切豆腐上方时 row_begin 增加，切豆腐右方时 column_end 减小，切豆腐下方时 row_end 减小，切豆腐左方时 column_begin增加。

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

代码实现

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

class Solution {
public:
    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;
    }
};

以思路一为例进行调试

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

class Solution {
public:
    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}} ;
	Solution s;
	vector<int> ans=s.spiralOrder(matrix);
	for(const auto i:ans){
		cout<<i<<" ";
	}
	return 0;
}

LeetCode 面试经典 150_矩阵_螺旋矩阵（35_54)原题链接
欢迎大家和我沟通交流(✿◠‿◠)