• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

LeetCode 59. 螺旋矩阵 II【c++/java详细题解】

互联网 diligentman 2小时前 2次浏览

1、题目

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

示例 1:

LeetCode 59. 螺旋矩阵 II【c++++/java详细题解】

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

示例 2:

输入:n = 1
输出:[[1]]

提示:

  • 1 <= n <= 20

2、思路

(模拟)

O

(

n

2

)

O(n^2)

O(n2)

给定一个正整数n,让我们生成一个包含 1n^2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

样例:

LeetCode 59. 螺旋矩阵 II【c++++/java详细题解】

如样例所示,n = 3 , 我们输出[[1,2,3],[8,9,4],[7,6,5]],下面来讲解模拟的做法。

具体过程如下:

1、我们顺时针定义四个方向:上右下左。d = 0表示向右走,d = 1表示向下走,d = 2表示向左走,d = 3表示向上走,方向偏移数组定义为 dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0},如下图所示:

LeetCode 59. 螺旋矩阵 II【c++++/java详细题解】

2、当前位置定义为(x,y),使用d = (d + 1) % 4来更改方向,那么下个要走的位置(a, b)则表示为: a = x + dx[d], b = y + dy[d]

3、从左上角开始遍历&#xff0c++;先往右走,走到不能走为止,然后更改到下个方向,再走到不能走为止,依次类推,遍历

n

2

n^2

n2 个格子后停止。

时间复杂度分析: 矩阵中的每个数都被遍历一次,因此时间复杂度为

O

(

n

2

)

O(n^2)

O(n2)

n

n

n是给定的正整数。

3、c++++代码

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>>res(n, vector<int>(n, 0));
        int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};  //方向偏移数组
        int x = 0, y = 0;  //当前位置
        for(int i = 1, d = 0; i <= n*n; i++)
        {
            res[x][y] = i; 
            int a = x + dx[d], b = y + dy[d]; 
            if(a <0 || a == n || b < 0 || b == n || res[a][b]){  //出界或者该位置已经被走过
                d = (d + 1) % 4;   //更改方向
                a = x + dx[d], b = y + dy[d];  //下一个要走的位置
            }
            x = a, y = b;    
        }
        return res;
    }
};

4、java代码

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};  //方向偏移数组
        int x = 0, y = 0;  //当前位置
        for(int i = 1, d = 0; i <= n*n; i++)
        {
            res[x][y] = i; 
            int a = x + dx[d], b = y + dy[d]; 
            if(a <0 || a == n || b < 0 || b == n || res[a][b] != 0){  //出界或者该位置已经被走过
                d = (d + 1) % 4;   //更改方向
                a = x + dx[d] ; 
                b = y + dy[d];  //下一个要走的位置
            }
            x = a;
            y = b;    
        }
        return res;
    }
}

原题链接: 59. 螺旋矩阵 II
LeetCode 59. 螺旋矩阵 II【c++++/java详细题解】


程序员灯塔
转载请注明原文链接:LeetCode 59. 螺旋矩阵 II【c++/java详细题解】
喜欢 (0)