[LeetCode] Spiral Matrix 螺旋矩阵

简介:

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

这道题让我们将一个矩阵按照螺旋顺序打印出来,我们只能一条边一条边的打印,首先我们要从给定的mxn的矩阵中算出按螺旋顺序有几个环,注意最终间的环可以是一个数字,也可以是一行或者一列。环数的计算公式是 min(m, n) / 2,知道了环数,我们可以对每个环的边按顺序打印,比如对于题目中给的那个例子,个边生成的顺序是(用颜色标记了数字) Red -> Green -> Blue -> Yellow -> Black 

1 2 3

4 5 6

7 8 9

我们定义p,q为当前环的高度和宽度,当p或者q为1时,表示最后一个环只有一行或者一列,可以跳出循环。此题的难点在于下标的转换,如何正确的转换下标是解此题的关键,我们可以对照着上面的3x3的例子来完成下标的填写,代码如下:

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> res;
        if (matrix.empty() || matrix[0].empty()) return res;
        int m = matrix.size(), n = matrix[0].size();
        int c = m > n ? (n + 1) / 2 : (m + 1) / 2;
        int p = m, q = n;
        for (int i = 0; i < c; ++i, p -= 2, q -= 2) {
            for (int col = i; col < i + q; ++col) 
                res.push_back(matrix[i][col]);
            for (int row = i + 1; row < i + p; ++row)
                res.push_back(matrix[row][i + q - 1]);
            if (p == 1 || q == 1) break;
            for (int col = i + q - 2; col >= i; --col)
                res.push_back(matrix[i + p - 1][col]);
            for (int row = i + p - 2; row > i; --row) 
                res.push_back(matrix[row][i]);
        }
        return res;
    }
};

本文转自博客园Grandyang的博客,原文链接:螺旋矩阵[LeetCode] Spiral Matrix ,如需转载请自行联系原博主。

相关文章
Leetcode 74. Search a 2D Matrix
这道题很简单,为此专门写篇博客其实算博客凑数了。给你一个每一行每一列都是增序,且每一行第一个数都大于上一行末尾数的矩阵,让你判断某个数在这个矩阵中是否存在。 假设矩阵是m*n,扫一遍的时间复杂度就是O(m*n),题目中给出的这么特殊的矩阵,时间复杂度可以降到O(m+n),具体代码如下,写的比较挫。
83 1
Leetcode 240. Search a 2D Matrix II
具体思路就是每一行倒着扫,扫到第一个比target小的数就跳到下行,如果等于当然是直接返回true了,如果下一行还比target小就继续跳下一行,直到最后一行。 为啥这么做是可行的? 可能我比较笨,想了半天才想到。 因为每一列都是增序的,举个例子,假设matrix[0][5] > target,那么[0][5]位置右下(包含右和下)所有元素不可能比target小。
46 0
【Leetcode -2181.合并零之间的节点- 2326.螺旋矩阵Ⅳ】
【Leetcode -2181.合并零之间的节点- 2326.螺旋矩阵Ⅳ】
73 0
|
1月前
|
C++
Leetcode第54题(螺旋矩阵)
这篇文章介绍了LeetCode第54题“螺旋矩阵”的解题思路和C++的实现代码,该题目要求按照顺时针螺旋顺序返回给定矩阵中的所有元素。
14 1
Leetcode第54题(螺旋矩阵)
|
1月前
【LeetCode 05】螺旋矩阵II总结
【LeetCode 05】螺旋矩阵II总结
14 0
|
3月前
|
算法
LeetCode第59题螺旋矩阵 II
LeetCode第59题"螺旋矩阵 II"的解题方法,通过模拟螺旋填充过程,一圈一圈从外到内按顺序填充数字,直到完成整个矩阵的构建。
LeetCode第59题螺旋矩阵 II
|
3月前
|
存储 算法
LeetCode第54题螺旋矩阵
LeetCode第54题"螺旋矩阵"的解题方法,通过模拟从外到内的螺旋遍历过程,并利用方向向量控制遍历方向的转换,有效输出矩阵的螺旋顺序。
LeetCode第54题螺旋矩阵
|
机器学习/深度学习 算法
代码随想录Day02 数组基础2 leetcode T977有序数组的平方, T209 长度最小的子数组,T59 螺旋矩阵II
代码随想录Day02 数组基础2 leetcode T977有序数组的平方, T209 长度最小的子数组,T59 螺旋矩阵II
56 0
|
5月前
leetcode54螺旋矩阵题解
leetcode54螺旋矩阵题解
31 2
|
5月前
|
算法 机器人 数据挖掘
LeetCode题目54:螺旋矩阵【python4种算法实现】
LeetCode题目54:螺旋矩阵【python4种算法实现】