54&59. 螺旋矩阵I&II

54. 螺旋矩阵

本题来自 LeetCode：54. 螺旋矩阵^[1]

题目描述

给定一个包含  m x n  个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例  1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例  2:

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

题目分析

本题按照逆时针，遍历二维数组即可。主要控制边界，判断是否越界。

题目解答

class Solution {
    public ListInteger spiralOrder(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new LinkedList();
        }
        ListInteger list = new LinkedList();

        int left = 0;
        int right = matrix[0].length - 1;
        int top = 0;
        int bottom = matrix.length - 1;

        while(left = right && top = bottom) {
            // 向右
            for(int i = left; i = right; i ++) {
                list.add(matrix[top][i]);
            }
            // 此时top行的元素已经处理完
            top ++;
            // 判断行是否越界
            if(top  bottom) {
                break;
            }
            // 向下
            for(int i = top; i = bottom; i ++) {
                list.add(matrix[i][right]);
            }
            // 此时right列的元素已经处理完
            right --;
            // 判断列是否越界
            if(left  right) {
                break;
            }
            // 向左
            for(int i = right; i = left; i --) {
                list.add(matrix[bottom][i]);
            }
            // 此时bottom行的元素已经处理完
            bottom --;
            // 判断行是否越界
            if(top  bottom) {
                break;
            }
            // 向上
            for(int i = bottom; i = top; i --) {
                list.add(matrix[i][left]);
            }
            // 此时left列的元素已经处理完
            left ++;
            // 判断列是否越界
            if(left  right) {
                break;
            }
        }

        return list;
    }
}

复杂度分析：
时间复杂度： O(m * n)
空间复杂度： O(m * n)

59. 螺旋矩阵 II

本题来自 LeetCode：59. 螺旋矩阵 II^[2]

题目描述

给定一个正整数  n，生成一个包含 1 到  n2  所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:

输入: 3
输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

题目分析

本题和 54. 螺旋矩阵类似。

题目解答

class Solution {
    public int[][] generateMatrix(int n) {
        if(n == 0) {
            return new int[0][0];
        }
        int[][] matrix = new int[n][n];

        int left = 0;
        int right = n - 1;
        int top = 0;
        int bottom = n - 1;
        int count = 0;
        // 总元素个数
        int totalCount = n * n;
        while(left = right && top = bottom) {
            // 向右
            for(int i = left; i = right && count = totalCount; i ++) {
                matrix[top][i] =  ++count;
            }
            // 此时top行的元素已经处理完
            top ++;
            // 向下
            for(int i = top; i = bottom && count = totalCount; i ++) {
                matrix[i][right] = ++count;
            }
            // 此时right列的元素已经处理完
            right --;
            // 向左
            for(int i = right; i = left && count = totalCount; i --) {
                matrix[bottom][i] = ++ count;
            }
            // 此时bottom行的元素已经处理完
            bottom --;
            // 向上
            for(int i = bottom; i = top && count = totalCount; i --) {
                matrix[i][left] = ++ count;
            }
            // 此时left列的元素已经处理完
            left ++;
        }

        return matrix;
    }
}

复杂度分析：
时间复杂度： O(n * n)
空间复杂度： O(n * n)

参考资料

54. 螺旋矩阵: https://leetcode-cn.com/problems/spiral-matrix

55. 螺旋矩阵 II: https://leetcode-cn.com/problems/spiral-matrix-ii/

原文始发于微信公众号（xiaogan的技术博客）：