【LeetCode面试150】——54螺旋矩阵
博客昵称：沈小农学编程
作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！
PS：哈喽！各位CSDN的uu们，我是你的小弟沈小农，希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
题目难度：中等
默认优化目标：最小化时间复杂度。
Python默认为Python3。
目录
1 题目描述
2 题目解析
3 算法原理及代码实现
3.1 按层模拟
参考文献
1 题目描述
给你一个 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
2 题目解析
输入是一个m行n列的矩阵matrix，输出是一维数组ans。约束条件是顺时针螺旋输出matrix中的元素。
大致流程如下所示：
3 算法原理及代码实现
3.1 按层模拟
我们可以按层(行，列)将矩阵分解，先输出外层的元素，再输出次外层的数据，一次类推。
我们初始化4个指针：top指向matrix第一行；left指向matrix第一列；bottom指向matrix最后一行；right指向matrix最后一列。然后按照以下步骤将matrix中元素压入ans。
① 从左到右遍历上侧元素，从(top,left)到(top,right)
② 从上到下遍历右侧元素，从(top+1,right)到(bottom,right)
当left<right和top<bottom
③ 从右往左输出下侧元素，从(bottom,right-1)到(bottom,left+1)
④ 从下到上输出左侧元素，从(bottom,left)到(top+1,left)
之后left++;top++;right--;bottom--;
算法流程图如下：
时间复杂度为O(mn)。不算ans的空间，则空间复杂度为O(1)。
C++代码实现
class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int m=matrix.size(),n=matrix[0].size();
if(!(m*n)) return {};vector<int> ans;int top=0,left=0,bottom=m-1,right=n-1;while(top<=bottom && left<=right){for(int column=left;column<=right;column++){ans.push_back(matrix[top][column]);}for(int row=top+1;row<=bottom;row++){ans.push_back(matrix[row][right]);}if(top<bottom && left<right){for(int column=right-1;column>left;column--){ans.push_back(matrix[bottom][column]);}for(int row=bottom;row>top;row--){ans.push_back(matrix[row][left]);}}left++;right--;top++;bottom--;} return ans;
}
};Python代码实现
class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:m,n=len(matrix),len(matrix[0])if m*n==0:return list()ans=list()left,right,top,bottom=0,n-1,0,m-1while left<=right and top<=bottom:for column in range(left,right+1,1):ans.append(matrix[top][column])for row in range(top+1,bottom+1,1):ans.append(matrix[row][right])if left<right and top<bottom:for column in range(right-1,left,-1):ans.append(matrix[bottom][column])for row in range(bottom,top,-1):ans.append(matrix[row][left])left+=1right-=1top+=1bottom-=1return ans参考文献
力扣面试经典150题
力扣官方题解