【每日算法Day 5】顺时针打印矩阵

题目链接

LeetCode 54. 顺时针打印矩阵 (opens new window)

题目描述

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

示例

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

解题思路

可以模拟贪吃蛇移动，建立一个等大小的辅助布尔型数组标记某位置是否访问过。向右移动时遇到数组右侧边界或已访问过的点则向下。向下、向左、向上同理。时间复杂度为O(mn)因为每个点都要访问一次，空间复杂度也为O(mn)。

为避免使用额外的O(m*n)的空间，由于本题是由外到内访问的，访问过程中可访问区域的上边界、右边界、下边界、左边界依次-1，则可用四个变量标记四个边界并在一次单向访问结束后调整，遍历时只需判断相应值是否到达边界即可。

public int[] spiralOrder(int[][] matrix) {
    if (matrix==null||matrix.length == 0||matrix[0].length==0) {
        return new int[0];
    }
    int[] res = new int[matrix.length * matrix[0].length];
    int u = 0, d = matrix.length - 1, l = 0, r = matrix[0].length - 1;
    int idx = 0;
    while (true) {
        for (int i = l; i <= r; i++) {
            res[idx++] = matrix[u][i];
        }
        if (++u > d) {
            break;
        }
        for (int i = u; i <= d; i++) {
            res[idx++] = matrix[i][r];
        }
        if (--r < l) {
            break;
        }
        for (int i = r; i >= l; i--) {
            res[idx++] = matrix[d][i];
        }
        if (--d < u) {
            break;
        }
        for (int i = d; i >= u; i--) {
            res[idx++] = matrix[i][l];
        }
        if (++l > r) {
            break;
        }
    }
    return res;
}

总结

一开始我做这题的时候因为不确定四个方向具体的访问次数，写了四个方法goRight(),goDown(),goLeft(),goUp()互相调用并将布尔数组设为全局变量来辅助判断，这样写代码不够简洁并且增加额外的调用栈。其实用循环的话外层可为死循环，在内部状态转换的时候判断是否满足继续的条件，不满足则跳出循环。