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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)