题解 | #螺旋矩阵(二)#

螺旋矩阵(二)

http://www.nowcoder.com/practice/2c8078a728834e81a046fdefdea049aa

题目：

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

方法一：按层模拟

按层模拟，先填外层数字，再填内层数字，直到所有数字填完就可以结束循环：

因此每一行有一个rowStart和rowEnd，每一列有colStart和colEnd,先从外层填起，每一圈都是 $[c o l S t a r t, c o l E n d] = > [r o w S a r t + 1, r o w E n d] = > [c o l E n d - 1, c o l S t a r t] = > [r o w E n d - 1, r o w S t a r t + 1]$ ,填完一圈后，rowStart和colStart需要加一，rowEnd和colEnd需要减一。

alt

java
javascript

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型二维数组
     */
    public int[][] Matrix (int n) {
        // write code here
        int[][]res=new int[n][n];
        int rowstart=0,colstart=0,rowend=n,colend=n,cnt=1;
        while(cnt<=n*n){
            for(int i=colstart;i<colend;i++){//模拟从左到右
                if(cnt<=n*n)res[rowstart][i]=cnt++;
            }
            for(int i=rowstart+1;i<rowend;i++){
                if(cnt<=n*n)res[i][colend-1]=cnt++;//模拟从上到下
            }
            for(int i=colend-2;i>=colstart;i--){
                if(cnt<=n*n)res[rowend-1][i]=cnt++;//从右到左
            }
            for(int i=rowend-2;i>rowstart;i--){
                if(cnt<=n*n)res[i][colstart]=cnt++;//从下到上
            }
            rowstart+=1;
            colstart+=1;
            rowend-=1;
            colend-=1;
        }
        return res;
   
    }
}

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
        res=Array(n).fill().map(()=>Array(n));
        let rowstart=0,colstart=0,rowend=n,colend=n,cnt=1;
        while(cnt<=n*n){
            for(let i=colstart;i<colend;i++){
                if(cnt<=n*n)res[rowstart][i]=cnt++;
            }
            for(let i=rowstart+1;i<rowend;i++){
                if(cnt<=n*n)res[i][colend-1]=cnt++;
            }
            for(let i=colend-2;i>=colstart;i--){
                if(cnt<=n*n)res[rowend-1][i]=cnt++;
            }
            for(let i=rowend-2;i>rowstart;i--){
                if(cnt<=n*n)res[i][colstart]=cnt++;
            }
            rowstart+=1;
            colstart+=1;
            rowend-=1;
            colend-=1;
        }    
        return res;

};

复杂度：

时间复杂度： $O(n^{2})$ ,双重循环
空间复杂度： $O (n)$ ,额外开辟一个数组

方法二：矩阵模拟

按照题目所说是右下左上的顺时针填入数字，因此我们的关注点就在于如何找到下一个位置，设置一个数组directions保存右下左上四个方向，directIndex标志是否需要换方向，当取到的下一个坐标不合法或者填过数字，说明需要换方向，更新direcIndex，最后根据更新后的direcIndex更新坐标。

java
javascript

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型二维数组
     */
    public int[][] Matrix (int n) {
        // write code here
         int[][]res=new int[n][n];
        int[][]directions={{0,1},{1,0},{0,-1},{-1,0}};//右下左上顺时针方向
        int cnt=1,directIndex=0,row=0,col=0;//填入数字，方向，所处行数，列数
        while(cnt<=n*n){
            res[row][col]=cnt++;
            int nextRow=row+directions[directIndex][0],nextCol=col+directions[directIndex][1];
            if(nextRow<0||nextRow>=n||nextCol<0||nextCol>=n||res[nextRow][nextCol]!=0){//如果下一个位置不合法或者位置合法但是已经填入数字就应该转方向
                directIndex=(directIndex+1)%4;
            }
            row=row+directions[directIndex][0];//更新行数列数
            col=col+directions[directIndex][1];
        }
        
        return res;
   
    }
}

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
         res=Array(n).fill().map(()=>Array(n).fill(0));
         directions=[[0,1],[1,0],[0,-1],[-1,0]];//右下左上顺时针方向
        let cnt=1,directIndex=0,row=0,col=0;//填入数字，方向，所处行数，列数
        while(cnt<=n*n){
            res[row][col]=cnt++;
            let nextRow=row+directions[directIndex][0],nextCol=col+directions[directIndex][1];
            if(nextRow<0||nextRow>=n||nextCol<0||nextCol>=n||res[nextRow][nextCol]!=0){//如果下一个位置不合法或者位置合法但是已经填入数字就应该转方向
                directIndex=(directIndex+1)%4;
            }
            row=row+directions[directIndex][0];//更新行数列数
            col=col+directions[directIndex][1];
        }
         
        return res;

};