题解 | #顺时针打印矩阵#

描述

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

算法

我们的目标是按照图中的数字大小顺序访问每个位置的值，然后按顺序保存每个点。

方法一

我们定义一个从 (0, 0) 出发的点，当遇到边界或者访问过的点之后就向右转，已经访问过的点就把它的值赋为一个不可能的值 inf。
如下图，我们访问到边界情况时就向右转

如下图，当我们访问到 12 的下一个点的时候就向右转

代码实现如下（python版代码注释参照c++版）：

// c++
class Solution {
public:
    const int inf = 0x3f3f3f3f; // 访问过的值标记为 inf
    int x[4] = {0, 1, 0, -1}, y[4] = {1, 0, -1, 0}; // x, y 分别是行、列两个方向的向右换方向的顺序
    vector<int> printMatrix(vector<vector<int> > mat) {
        vector<int> res;
        int n = mat.size(), m = mat[0].size();
        int a = 0, b = 0, idx = 0;

        // 一共会访问 m * n 次，循环结束之后就代表所有点都访问过了一次
        for (int i = 0; i < m * n; i++) {
            res.push_back(mat[a][b]);
            mat[a][b] = inf; // 把访问过的值改成 inf
            int s = a + x[idx], t = b + y[idx]; // s, t 是下一个访问的值

            // 如果越界或者遇到访问过的值就需要换方向
            if (s < 0 || s >= n || t < 0 || t >= m || mat[s][t] == inf) {
                idx = (idx + 1) % 4; // 按照顺序改变遍历的方向
                s = a + x[idx], t = b + y[idx]; // 修正越界的 s, t 到合法的方向
            }
            a = s, b = t; // s, t 是合法的下一个访问节点
        }
        return res;
    }
};

# python3
class Solution:
    def printMatrix(self, mat):
        dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        inf = 0x3f3f3f3f
        i, j, idx = 0, 0, 0
        n, m = len(mat), len(mat[0])
        res = []
        for _ in range(n * m):
            res.append(mat[i][j])
            mat[i][j] = inf
            a, b = i + dir[idx][0], j + dir[idx][1]
            if a < 0 or a >= n or b < 0 or b >= m or mat[a][b] == inf:
                idx = (idx + 1) % 4
                a, b = i + dir[idx][0], j + dir[idx][1]
            i, j = a, b
        return res

因为我们把所有的节点都访问了一次，所以时间复杂度是 O(m * n)

方法二

方法二用python实现比较简单，其他语言不推荐使用。我们可以把原二维数组想象成一个木板，每次拆去四个方向的边框。
原来的样子

拆去上方边框

拆去右边边框

直到二维矩阵消失。注意要判断每次拆去边框之前矩阵是否合法。

# python3
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, mat):
        res = []
        while mat:
            res += mat[0]
            mat.pop(0)
            if not mat or not mat[0]: break // 判断矩阵是否合法
            for i in range(len(mat)):
                res += [mat[i][-1]]
                mat[i].pop(-1)
            if not mat: break // 判断矩阵是否合法
            res += mat[-1][::-1]
            mat.pop(-1)
            if not mat or not mat[0]: break // 判断矩阵是否合法
            for i in range(len(mat) - 1, -1, -1):
                res += [mat[i][0]]
                mat[i].pop(0)
        return res

即使我们有的时候是直接弹出了整个一维数组，但是 append 实际上是复制了整个数组，所以最终我们的时间复杂度还是 O(m * n)。