【leetcode】10. 数组-顺时针打印矩阵

发表于 更新于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
难易程度：easy

示例 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]
 
限制：
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

分析

本题本质上一个模拟过程,设矩阵上右下左的范围一次是top = 0,right = n - 1,button = m - 1,left = 0：

  1. left->right：上侧从左到右，i = left; lmatrix[top][i]; i++，遍历完后top这一行需要丢弃，top++
  2. top->button：右侧从上到下，i = top; matrix[i][right]; i++，遍历完后right这一列需要丢弃，right--
  3. right->left：下侧从右到左，i = right; matrix[button][i]; i--，遍历完后button这一行需要丢弃，button--
  4. button->top：左侧从下到上，i = button; matrix[i][left]; i++，遍历完后left这一列需要丢弃，left++

时间复杂度：O(N^2)
空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int m = matrix.size();
        if (m == 0) {
            return res;
        }
        int n = matrix[0].size();
        int left = 0, right = n - 1, top = 0, button = m - 1;
        
        while(true) {
            for (int i = left; i <= right; i++) {
                res.push_back(matrix[top][i]);
            }
            if (++top > button) break;

            for (int i = top; i <= button; i++) {
                res.push_back(matrix[i][right]);
            }
            if (--right < left) bareak;

            for (int i = right; i >= left; i--) {
                res.push_back(matrix[button][i]);
            }
            if (--button < top) break;

            for (int i = button; i >= top; i--) {
                res.push_back(matrix[i][left]);
            }
            if (++left > right) break;
        }
        return res;
    }
};