剑指offer(C++)-JZ29：顺时针打印矩阵(算法-模拟)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：

[[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]

则依次打印出数字

[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

数据范围:

0 <= matrix.length <= 100

0 <= matrix[i].length <= 100

示例：

输入：

[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]

返回值：

[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

解题思路：

本题考察算法场景模拟。两种解题思路。

1）模拟边界

       将矩阵看成多层包裹，先顺时针遍历最外面一层，再进入里面一层继续遍历，直到上下左右边界交错。

2）螺旋矩阵

       环带为一层遍历，边界为一层遍历。边界遍历又分为上下左右四个子部分。以“1+4”的组合遍历，完成螺旋矩阵。

测试代码：

1）模拟边界

class Solution {
public:
    vector<int> printMatrix(vector<vector<int>> matrix) {
        vector<int> result;
        int size = int(matrix.size());
        // 处理矩阵为空的情况
        if(size == 0) 
            return result;
        // 左边界
        int left = 0; 
        // 右边界
        int right = matrix[0].size() - 1; 
        // 上边界
        int up = 0; 
        // 下边界
        int down = size - 1; 
        // 循环直到边界交错
        while(left <= right && up <= down){ 
            // 上边界从左到右
            for(int i = left; i <= right; i++) 
                result.push_back(matrix[up][i]); 
            // 上边界向下一格，并判断上下边界位置是否交错
            up++; 
            if(up > down)
                break;
            // 右边界从上到下
            for(int i = up; i <= down; i++) 
                result.push_back(matrix[i][right]);
            // 右边界向左一格，并判断左右边界位置是否交错
            right--; 
            if(left > right)
                break;
            // 下边界从右到左
            for(int i = right; i >= left; i--) 
                result.push_back(matrix[down][i]);
            // 下边界向上一格，并判断上下边界位置是否交错
            down--; 
            if(up > down)
                break; 
            // 左边界从下到上
            for(int i = down; i >= up; i--) 
                result.push_back(matrix[i][left]);
            // 左边界向右一格，并判断左右边界位置是否交错
            left++; 
            if(left > right)
                break;
        }
        return result;
    }
};

2）螺旋矩阵

class Solution {
public:
    vector<int> printMatrix(vector<vector<int>> matrix) {       
        int row = int(matrix.size());
        int col = int(matrix[0].size());
        // 处理矩阵为空的情况
        if(row == 0 || col == 0) 
            return vector<int>(0);
        // 确认环数，环数与行列的最小值有关
        int minL = min(row, col);
        int ring = minL / 2 + minL % 2;
        // 螺旋矩阵遍历
        int count = row * col;
        int t = 0;
        vector<int> result(count);
        for(int k = 0; k < ring; ++k){
            // 当前环上边界遍历
            for(int p = k; p < col - k && t < count; ++p){
                result[t++] = matrix[k][p];
            }
            // 当前环右边界遍历
             for(int p = k + 1; p < row - k - 1 && t < count; ++p){
                result[t++] = matrix[p][col - k - 1];
            }
            // 当前环下边界遍历
             for(int p = col - k - 1; p >= k && t < count; --p){
                result[t++] = matrix[row - k - 1][p];
            }
            // 当前环左边界遍历
             for(int p = row - k - 2; p >= k + 1 && t < count; --p){
                result[t++] = matrix[p][k];
            }
        }
        return result;
    }
};