☆打卡算法☆LeetCode 54、螺旋矩阵 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个矩阵，按顺时针螺旋顺序，返回矩阵中的所有元素。”

题目链接：

来源：力扣（LeetCode）

链接：54. 螺旋矩阵 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给你一个 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]

二、解题

1、思路分析

这道题要模拟螺旋矩阵的路径，初始位置在左上角，初始方向是向右，当路径超出界限或进入之前访问的位置时，顺时针旋转，进入下一个方向。

所以，需要判断路径是否进入之前访问的位置，然后判断路径是否结束。

只要矩阵中的每个元素都被访问一次，矩阵中的元素数量就是路径的长度，路径的长度达到矩阵中元素数量时就将该路径返回。

2、代码实现

代码参考：

public class Solution {
    public IList<int> SpiralOrder(int[][] matrix) {
        List<int> res = new List<int>();
        int r1 = 0, r2 = matrix.Length - 1;
        if(r2==-1) return res;
            int c1 = 0, c2 = matrix[0].Length - 1;
            while(r1<=r2 && c1<=c2)
            {
                for (int i = c1; i <= c2; i++) res.Add(matrix[r1][i]);
                for (int i = r1 + 1; i <=r2; i++) res.Add(matrix[i][c2]);
                if(r1<r2 && c1<c2)
                {
                    for (int i = c2 - 1; i>= c1; i--) res.Add(matrix[r2][i]);
                    for (int i = r2 - 1; i > r1; i--) res.Add(matrix[i][c1]);
                }
                r1++;
                r2--;
                c1++;
                c2--;
            }
            return res;
    }
}

3、时间复杂度

时间复杂度 ： O(mn)

其中 mm 和 nn 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

空间复杂度： O(mn)

其中 mm 和 nn 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

三、总结

这个解题方法，需要记录已经走过的路径，所以时间复杂度比较高。

还可以设定上下左右的边界，然后上下边界交错，说明遍历结束，跳出循环，得到答案。

这种方法执行用时和内存消耗都比较少，可以优化一下算法。