题目描述

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

示例:

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

https://leetcode-cn.com/problems/spiral-matrix-ii/

解法1

本题目与“54. 螺旋矩阵”相似,但本题目给出矩阵的维度,要求生成螺旋矩阵。因为题目给出的是方阵,那么我们不需要考虑54题中内部出现孤立的一行或一列的情况。但会出现孤立一个元素的情况。

图1 3×3的螺旋方阵

我们按照顺时针的顺序一次从左到右、从上到下遍历round圈即可。通过举例子的方式,我们可以算出round=ceil(n/2)。下面我们来说如何处理孤立元素的情况。例如上述3×3的方阵,当遍历完外面一圈的数字后将会只留下一个数字。那么如何判定循环遇到这种情况了呢?以3×3的矩阵为例,当round=1时中心只剩下一个元素,而矩阵遍历完一圈会消耗掉左右两个数字。因此,我们可以推测当n-2*round=1时,矩阵遍历到中心元素。这是一个corner case,我们需要独立处理这种情况,全部代码如下所示。

class Solution {
    public int[][] generateMatrix(int n) {
        if (n < 0)
            return null;
        int[][] res = new int[n][n];


        int nRound = (int) Math.ceil(n / 2.0);
        int p = 1;

        for (int round = 0; round < nRound; round++) {
            int row = round, col = round;

            // 处理中心只包含一个元素的情况
            if (n - 2 * round == 1) {
                res[row][col] = p;
                break;
            }

            for (int i = 0; i < n - 2 * round - 1; i++)
                res[row][col++] = p++;

            for (int i = 0; i < n - 2 * round - 1; i++)
                res[row++][col] = p++;

            for (int i = 0; i < n - 2 * round - 1; i++)
                res[row][col--] = p++;

            for (int i = 0; i < n - 2 * round - 1; i++)
                res[row--][col] = p++;
        }

        return res;
    }
}
pwrliang Algorithms, Trick

Leave a Reply

Your email address will not be published. Required fields are marked *