54. 螺旋矩阵

[xiwenAndlejian]

54. 螺旋矩阵

思路

题目要求：对一个m行n列的矩阵，按照顺时针螺旋顺序返回所有元素。

可以采用分治的思想，将需要处理的矩阵一层一层拆分，可以得到以下情况：

• 空心方环：对应螺旋顺序下矩阵当前层数需要返回的元素。从起点(索引最小的节点)开始，依次按照四个方向(左->右、上->下、右->左、下->上)遍历完该层所有元素。
• 一列或一行：当n或m中至少有一个为奇数时，最后一层只需要沿一个方向遍历该层元素。

根据上述分析，我们实际需要记录当前坐标的索引(x行，y列)以及沿此方向需遍历的元素个数即可。

方环四个边的长度

我们假设层数(level)从0开始。可以看出level的最大值为max(level) = min(m, n)/2。

而方环实际上可以看作一个长方形，因此只需要知道它的长和宽就能知道它四个边对应的长度。

• 长 = m - 2 * level - 1，对应沿横向边的元素个数。
• 宽 = n - 2 * level - 1，对应沿纵向边的元素个数。

同理：最后一行(列)的长度也对应上述表达式。

解

public List<Integer> spiralOrder(int[][] matrix) {

    List<Integer> r = new LinkedList<>();
    if (matrix.length == 0)
        return r;
    int m = matrix.length, n = matrix[0].length;// Xmax = n - 1, Ymax = m - 1
    int min   = m > n ? n : m;
    for (int level = 0; (level << 1) < min; level++) {
        int x = n - 2 * level - 1, y = m - 2 * level - 1;
        int i = level, j = level;
        if (x == 0) {
            for (int s = 0; s <= y; s++)
                r.add(matrix[i++][j]);
        } else if (y == 0) {
            for (int s = 0; s <= x; s++)
                r.add(matrix[i][j++]);
        } else {
            for (int s = 0; s < x; s++)
                r.add(matrix[i][j++]);
            for (int s = 0; s < y; s++)
                r.add(matrix[i++][j]);
            for (int s = 0; s < x; s++)
                r.add(matrix[i][j--]);
            for (int s = 0; s < y; s++)
                r.add(matrix[i--][j]);
        }
    }
    return r;
}