返回

[Leetcode]59. Spiral Matrix II(C++)

题目描述

题目链接:59. Spiral Matrix II

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

例子

例子 1

Input: n = 3 Output: [[1,2,3],[8,9,4],[7,6,5]]

例子 2

Input: n = 1 Output: [[1]]

Constraints

  • 1 <= n <= 20

解题思路

思路和 [Leetcode]54. Spiral Matrix(C++) 按层遍历,由于这道题固定了矩阵的两个维度是相同的,所以相对而言更简单一点,代码如下:

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> generateMatrix(int n) {
        std::vector<std::vector<int>> result(n, std::vector<int>(n, 0));
        int row = 0;
        int step = 1;
        while (row < n / 2) {
            for (int i = row; i < n - row - 1; ++i) {
                result[row][i] = step;
                step++;
            }
            for (int i = row; i < n - row - 1; ++i) {
                result[i][n - row - 1] = step;
                step++;
            }
            for (int i = n - 1 - row; i > row; --i) {
                result[n - row - 1][i] = step;
                step++;
            }
            for (int i = n - 1 - row; i > row; --i) {
                result[i][row] = step;
                step++;
            }
            row++;
        }

        if (n % 2 == 1) {
            result[row][row] = step;
        }

        return result;
    }
};
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n^2) —> 返回值所需空间

GitHub 代码同步地址: 59.SpiralMatrixIi.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy