本文主要是介绍【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题
力扣官方题解
这篇关于【LeetCode面试150】——54螺旋矩阵的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!