剑指offer第19题 顺时针打印矩阵 C++

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.

解析

1. 直接处理矩阵：
   （1）从左到右输出第一行
   （2）从上到下输出最后一列
   （3）从右到左输出最后一行
   （4）从下到上输出第一列
   （5）缩小矩阵，重复上述处理
   技巧：使用4个变量left、right、top、bottom表示矩阵的左右上下边界，每次完成步骤1-4后缩小边界。
   注意：应该在出现左右边界或上下边界相邻时结束循环，即right=left和top=bottom时结束循环。此时导致循环结束的情况有4种：剩下一行、剩下一列、剩下一个元素、已经完成，对四种情况进行判断即可。

代码：

vector<int> printMatrix(vector<vector<int>> matrix) {
    vector<int> result;
    if (matrix.empty()) result;

    int col, row, count;
    col = matrix.size();
    row = matrix[0].size();
    count = col * row;

    //矩阵的左右上下边界
    int left, right,  top, bottom;
    left = 0;
    right = row - 1;
    top = 0;
    bottom = col - 1;

    //每次循环打印一圈,仅剩下一行或一列时退出
    while (left < right && top < bottom) {
        //left to right
        for (int i = left; i <= right; i++) {
            result.push_back(matrix[top][i]);
            count--;
        }

        //top to bottom
        for (int i = top + 1; i <= bottom; i++) {
            result.push_back(matrix[i][right]);
            count--;
        }

        //right to left
        for (int i = right - 1; i >= left; i--) {
            result.push_back(matrix[bottom][i]);
            count--;
        }

        //bottom to top
        for (int i = bottom - 1; i > top; i--) {
            result.push_back(matrix[i][left]);
            count--;
        }

        left++;
        top++;
        right--;
        bottom--;
    }

    //仅剩一列
    if (left == right && top != bottom) {
        for (int i = top; i <= bottom; i++) {
            result.push_back(matrix[i][left]);
            count--;
        }
    }
    //仅剩一行
    else if (left != right && top == bottom) {
        for (int i = left; i <= right; i++) {
            result.push_back(matrix[top][i]);
            count--;
        }
    }
    //仅剩一个元素
    else if (count > 0) {
        result.push_back(matrix[left][top]);
        count--;
    }

    return result;
}

2. 旋转矩阵：
   （1）输出原矩阵第一行
   （2）删除原矩阵第一行
   （3）逆时针旋转原矩阵
   （4）重复上面3个步骤，直至矩阵为空

代码：

/*逆时针旋转矩阵*/
vector<vector<int>> rotationMatrix(vector<vector<int>> matrix) {
    if (matrix.empty()) return matrix;

    int col = matrix.size();
    int row = matrix[0].size();
    if (col * row == 1) return matrix;

    vector<vector<int>> result(row);

    for (int j = row - 1; j >= 0; j--) {
        for (int i = 0; i < col; i++) {
            result[row - 1 - j].push_back(matrix[i][j]);
        }
    }
    return result;
}

/*主循环函数*/
vector<int> printMatrix(vector<vector<int>> matrix) {
    vector<int> result;

    while (1) {
        if (matrix.empty()) return result;
        int col = matrix.size();
        int row = matrix[0].size();
        vector<vector<int>> tmp(col - 1);
        //将第一行输出
        for (int i = 0; i < row; i++)
            result.push_back(matrix[0][i]);
        //删去第一行
        for (int i = 1; i < col; i++) {
            for (int j = 0; j <row; j++) {
                tmp[i - 1].push_back(matrix[i][j]);
            }
        }
        matrix = rotationMatrix(tmp);
    }
}