【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题

力扣官方题解