[剑指 Offer 第 2 版第 29 题] “顺时针打印矩阵”做题记录

第 29 题：顺时针打印矩阵

传送门：顺时针打印矩阵，牛客网 online judge 地址。

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

样例：

输入： [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ]

输出：[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

分析： + 这道题，书本上的解法我个人觉得还不够直观、简洁，要考虑到一些边界情况。 + 借用之前做题中，使用状态以及状态转移的策略，不难画出图形如下。

下面是对这张图的解释，我们只解释了一个状态执行的代码，其它状态可以同样分析得出。

• 在初始状态下，应该向右边走，因此状态为“RIGHT”（或许，这里定义成“方向”会更贴切一些）。
• 遍历完第 1 行，其实以后，我们都不会再遍历到横坐标为 0 的点，因此 row_min 加 1。
• 遍历完成以后，其实点的坐标越界了，我们要把它挪到下一次状态的起点。
• 如果遍历到中心的时候，很可能遇到只更改了状态，不执行循环体的情况，这就避免了对一些边界情况的考虑。

Java 代码：

  import java.util.ArrayList;

    // 29 顺时针打印矩阵
    // 参考资料：https://www.nowcoder.com/questionTerminal/9b4c81a02cd34f76be2659fa0d54342a
    public class Solution {

        private enum State {
            RIGHT, DOWN, LEFT, UP
        }

        public ArrayList<Integer> printMatrix(int[][] matrix) {
            ArrayList<Integer> res = new ArrayList<>();
            int row_max = matrix.length;
            if (row_max == 0) {
                return res;
            }
            int col_max = matrix[0].length;
            row_max--;
            col_max--;
            int row_min = 0;
            int col_min = 0;
            // 上面的代码虽然看起来行数比较多，但是其实只是做了极端情况的考虑和一些变量的初始化工作

            // 下面的代码虽然看起来比较长，但是也只是做了当前状态的判断以及状态转移，代码框架是一模一样的
            // 仔细体会这个过程，其实就是：每次接收一个状态，根据这个状态做出相应的操作，然后变更状态
            State state = State.RIGHT;
            int i = 0;
            int j = 0;
            while (row_min <= row_max && col_min <= col_max) {
                if (state == State.RIGHT) {
                    while (j <= col_max) {
                        res.add(matrix[i][j]);
                        j++;
                    }
                    j--;
                    i++;
                    state = State.DOWN;
                    row_min++;
                } else if (state == State.DOWN) {
                    while (i <= row_max) {
                        res.add(matrix[i][j]);
                        i++;
                    }
                    i--;
                    j--;
                    state = State.LEFT;
                    col_max--;
                } else if (state == State.LEFT) {
                    while (j >= col_min) {
                        res.add(matrix[i][j]);
                        j--;
                    }
                    j++;
                    i--;
                    state = State.UP;
                    row_max--;
                } else {
                    assert state == State.UP;
                    while (i >= row_min) {
                        res.add(matrix[i][j]);
                        i--;
                    }
                    i++;
                    j++;
                    state = State.RIGHT;
                    col_min++;
                }
            }
            return res;
        }

        public static void main(String[] args) {
            int[][] matrix1 = {{1, 2, 3, 4},
                    {5, 6, 7, 8},
                    {9, 10, 11, 12},
                    {13, 14, 15, 16}};
            int[][] matrix = new int[5][6];
            int count = 1;
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    System.out.print(count + "\t");
                    matrix[i][j] = count;
                    count++;
                }
                System.out.println();
            }
            Solution solution = new Solution();
            ArrayList<Integer> printMatrix = solution.printMatrix(matrix);
            System.out.println(printMatrix);
        }
    }

Python 代码：

  class Solution:
        # matrix类型为二维列表，需要返回列表
        def printMatrix(self, matrix):
            rows = len(matrix)
            cols = len(matrix[0])
            result = []
            if rows == 0 and cols == 0:
                return result
            left, right, top, buttom = 0, cols - 1, 0, rows - 1
            while left <= right and top <= buttom:
                for i in range(left, right + 1):
                    result.append(matrix[top][i])
                for i in range(top + 1, buttom + 1):
                    result.append(matrix[i][right])
                if top != buttom:
                    for i in range(left, right)[::-1]:
                        result.append(matrix[buttom][i])
                if left != right:
                    for i in range(top + 1, buttom)[::-1]:
                        result.append(matrix[i][left])
                left += 1
                top += 1
                right -= 1
                buttom -= 1
            return result

“大雪菜”的写法：我们顺时针定义四个方向：上右下左。从左上角开始遍历，先往右走，走到不能走为止，然后更改到下个方向，再走到不能走为止，依次类推，遍历 n^2 个格子后停止。

时间复杂度：矩阵中每个格子遍历一次，所以总时间复杂度是 O(n^2)。

C++ 代码：

  class Solution {
    public:
        vector<int> printMatrix(vector<vector<int>>& matrix) {
            vector<int> res;
            if (matrix.empty()) return res;
            int n = matrix.size(), m = matrix[0].size();
            vector<vector<bool>> st(n, vector<bool>(m, false));
            int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
            int x = 0, y = 0, d = 1;
            for (int k = 0; k < n * m; k ++ )
            {
                res.push_back(matrix[x][y]);
                st[x][y] = true;

                int a = x + dx[d], b = y + dy[d];
                if (a < 0 || a >= n || b < 0 || b >= m || st[a][b])
                {
                    d = (d + 1) % 4;
                    a = x + dx[d], b = y + dy[d];
                }
                x = a, y = b;
            }
            return res;
        }
    };

作者：yxc 链接：https://www.acwing.com/solution/AcWing/content/748/ 来源：AcWing 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/