描述

这是一篇针对初学者的题解。
知识点:矩阵
难度:一星


题解

题目抽象:给一个二维矩阵,顺时针转圈打印矩阵。
转圈是说:把矩阵最外层看成一个圈
##方法一:转圈打印
如果有个方法是顺时针转圈打印矩阵,那么我们可以先打印最外圈,然后再打印次外圈。
如图:

最外层为 [1 2 3 4 8 12 16 15 14 13 9 5]
次外层为 [6 7 11 10]
这里只有2层。
我们可以用矩阵的左上角和右下角唯一表示一个矩阵。设左上角坐标为(lx,ly), 右下角坐标为(rx,ry)

  1. 第一步:打印 [1 2 3 4]

  2. 第二步:打印 [8 12 16]

  3. 第三步:打印 [15 14 13]

  4. 第四步:打印 [8 5]
    因此可实现函数的代码为:

    // matrix原二维vector,ret 存打印结果的vector
    void print(int lx, int ly, int rx, int ry, vector<vector<int>> &matrix, vector<int> &ret) {
    
         for (int j=ly; j<=ry; ++j) ret.push_back(matrix[lx][j]);
         for (int i=lx+1; i<=rx; ++i) ret.push_back(matrix[i][ry]);
         int h = rx - lx + 1;
         if (h > 1) // 只有一行,不需要第三步
             for (int rj=ry-1; rj>=ly; --rj) ret.push_back(matrix[rx][rj]);
         int w = ry - ly + 1;
         if (w > 1) // 只有一列不需要第四步
             for (int ri = rx-1; ri>=lx+1; --ri) ret.push_back(matrix[ri][ly]);
     }

转圈打印函数已经实现好了,那么接下来每次打印一圈就好。缩小一圈就是lx+1, ly+1, rx-1, ry-1
因此本题代码为:

class Solution {
public:
    void print(int lx, int ly, int rx, int ry, vector<vector<int>> &matrix, vector<int> &ret) {

        for (int j=ly; j<=ry; ++j) ret.push_back(matrix[lx][j]);
        for (int i=lx+1; i<=rx; ++i) ret.push_back(matrix[i][ry]);
        int h = rx - lx + 1;
        if (h > 1)
            for (int rj=ry-1; rj>=ly; --rj) ret.push_back(matrix[rx][rj]);
        int w = ry - ly + 1;
        if (w > 1)
            for (int ri = rx-1; ri>=lx+1; --ri) ret.push_back(matrix[ri][ly]);
    }
    vector<int> printMatrix(vector<vector<int>>& matrix) {
        vector<int> ret;
        if (matrix.empty()) return ret;
        int lx = 0, ly = 0;
        int rx = matrix.size()-1, ry = matrix[0].size()-1;
        while (lx <= rx && ly <= ry) {
            print(lx++, ly++, rx--, ry--, matrix, ret);
        } 
        return ret;
    }

};

时间复杂度:O(mn), 矩阵中每个元素遍历一次
空间复杂度:O(m
n), 每个元素需要存下来