Leecode 59、54 |循序渐进理解螺旋矩阵

题目描述

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

输入: 3
输出:[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]]

解题思路

按照螺旋矩阵模拟即可，先从左到右，在从上到下，再从右到左，再从下到上。

每次进行cur++操作，直到累加到total为止。最后返回二维数组即可

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let top = 0, bottom =n-1
    let left = 0, right = n-1
    let res = []
    //必须先定义一层res[i] 否则无法为res添加res[i][j]  会报错
    for(let i=0;i<n;i++) res[i] = []
    let cur = 1, total = n*n
    while(cur<=total){
        for(let i=left;i<=right;i++) res[top][i] = cur++  // 从左到右
        top++
        for(let i=top;i<=bottom;i++) res[i][right] = cur++ // 从上到下
        right--
        for(let i=right;i>=left;i--) res[bottom][i] = cur++ // 从右到左
        bottom--
        for(let i=bottom;i>=top;i--) res[i][left] = cur++ // 从下到上
        left++
    }
    return res
};

复杂度分析

时间复杂度：O(n^2），其中 nn 是给定的正整数。矩阵的大小是 n imes nn×n，需要填入矩阵中的每个元素。

空间复杂度：O(1），除了返回的矩阵以外，空间复杂度是常数。

题目描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素

输入:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]
输出: [1,2,3,6,9,8,7,4,5]

输入:[  [1, 2, 3, 4],  [5, 6, 7, 8],  [9,10,11,12]]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

解题思路

和螺旋矩阵II 差不多，这个是让我么输出，而上次是让我们构造，还是按照螺旋矩阵模拟即可，先从左到右，在从上到下，再从右到左，再从下到上。

不过这里的矩阵行和列不相同了，可能会出现不成环的情况，那么最后会留一列或一行出来，这里借用一张图：

因此与上一题不同的是 ，从左到右、从上到下扫描后需要提前判断一下是否已经扫描完成，因为遍历顺序，如果最后留下一行的话，需要从左到右遍历，此时 top > bottom 。如果最后留下一列的话，需要从上到下遍历，此时 left > right。

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    //特殊情况处理
    if(!matrix.length) return []
    let n = matrix.length， m = matrix[0].length，total = n*m
    let top = 0,bottom = n-1，left = 0,right = m-1， res = []
     //退出循环条件 ： 已经扫描完整个数组
    while(res.length < total){
        for(let i=left;i<=right;i++) res.push(matrix[top][i]) // 从左到右
        top++
        for(let i=top;i<=bottom;i++) res.push(matrix[i][right]) // 从上到下
        right--
        /* 因为n 和 m 不相同的时候，最后可能会留一列或一行，避免重复计算，总数够了直接跳出去 亲身 
        经历不加这行可能会导致运行超时*/
        if(res.length === total) break
        for(let i=right;i>=left;i--) res.push(matrix[bottom][i]) // 从右到左
        bottom--
        for(let i=bottom;i>=top;i--) res.push(matrix[i][left]) // 从下到上
        left++
    }
    return res
};

复杂度分析

时间复杂度：O(mn)，其中 mm 和 nn 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

空间复杂度：O(1)。除了输出数组以外，空间复杂度是常数