(Leetcode 2021 刷题计划) 59. 螺旋矩阵 II

每日一题时间: 2020-03-16 题目链接: 59. 螺旋矩阵 II 官方题解链接: 螺旋矩阵 II

题目

给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

代码语言：txt复制

示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：
输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 20

解题方法

与 (Leetcode 2021 刷题计划) 54. 螺旋矩阵 解法类似, 仅是反向思考

按层模拟

代码语言：txt复制

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n, vector<int>(n));
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        int index = 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column  , index  ) {
                matrix[top][column] = index;
            }
            for (int row = top   1; row <= bottom; row  , index  ) {
                matrix[row][right] = index;
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--, index  ) {
                    matrix[bottom][column] = index;
                }
                for (int row = bottom; row > top; row--, index  ) {
                    matrix[row][left] = index;
                }
            }
            left  ;
            right--;
            top  ;
            bottom--;
        }
        return matrix;
    }
};

• 复杂度分析
  • 时间复杂度: O(MN)
  • 空间复杂度: O(1)
    • M 和 N 分别是输入矩阵的行数和列数

参考资料

1. 59. 螺旋矩阵 II
2. 螺旋矩阵 II

leetcode matrix

0 人点赞