描述

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

题解

题目抽象：给一个二维矩阵，顺时针转圈打印矩阵。
转圈是说：把矩阵最外层看成一个圈
##方法一：转圈打印
如果有个方法是顺时针转圈打印矩阵，那么我们可以先打印最外圈，然后再打印次外圈。
如图：
最外层为 [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(mn), 每个元素需要存下来