当前位置：首页 > article >正文

【LeetCode面试150】——54螺旋矩阵

article 2024/9/25 17:20:26

博客昵称：沈小农学编程

作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！

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-1
        while 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+=1
            right-=1
            top+=1
            bottom-=1
        return ans