首页 > 试题广场 >

螺旋矩阵-ii

[编程题]螺旋矩阵-ii

热度指数：10923 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个整数n，将数字1到 $n^2$ 按螺旋的顺序填入n×n的矩阵

例如：

给出的n=3，

你应该返回如下矩阵：

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

示例1

输入

输出

[[1,2],[4,3]]

算法知识视频讲解

Java

在刷题的他很想退休

import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型
     * @return int整型二维数组
     */
    public int[][] generateMatrix (int n) {
        int[][] arr = new int[n][n];
        if(n == 0){
            return arr;
        }
        int s = 0;
        int num = 2;
        int end = n * n;
        int i = 0;
        int j = 0;
        arr[0][0] = 1;
        for (int k = 1; k < end; k++) {
            if (s == 0) {
                j++;
            } else if (s == 1) {
                i++;
            } else if (s == 2) {
                j--;
            } else if (s == 3) {
                i--;
            }
            arr[i][j] = num++;
            if (s == 0 && (j >= n - 1 || arr[i][j + 1] != 0)) {
                s++;
            } else if (s == 1 && (i >= n - 1 || arr[i + 1][j] != 0)) {
                s++;
            } else if (s == 2 && (j == 0 || arr[i][j - 1] != 0)) {
                s++;
            } else if (s == 3 && (arr[i - 1][j] != 0)) {
                s = 0;
            }
        }
        return arr;
    }
}

发表于 2024-05-16 15:58:36 回复(0)

Java

牛客89636334号

/*每一个螺旋可以由起始位置确定，四角坐标表示为:
(start,start),(start,n-start-1)
(n-start-1,start),(n-start-1,n-start-1)
*/
        int[][] res = new int[n][n];
        int startIndex = 0;
        int val = 1;
        if (n < 1 || n > 1000) {
            return res;
        }
        while (startIndex <= (n - 1) / 2) {
            if (startIndex == (n - 1 / 2)) {
                res[startIndex][startIndex] = val;
                break;
            }

            for (int right = startIndex; right < (n - startIndex); right++) { //向右
                res[startIndex][right] = val;
                val++;
            }

            for (int height = startIndex + 1; height < (n - startIndex); height++) {//下
                res[height][n - startIndex - 1] = val;
                val++;
            }
            for (int left = (n - startIndex) - 2; left >= startIndex; left--) { //左
                res[n - startIndex - 1][left] = val;
                val++;
            }
            for (int up = (n - startIndex) - 2; up > startIndex; up--) { //上
                res[up][startIndex] = val;
                val++;
            }
            startIndex++;
        }
        return res;

发表于 2020-09-23 10:03:08 回复(0)

Java

追梦赤子心2019

我这个是O(n）级别的复杂度低

public class Solution {
    public int[][] generateMatrix(int n) {
        int num = n * n;
        int c = 0;
        int row = 1;
        int m = 1;
        int x = 0;
        int count = 0;

        count = n;  
        int[][] arr = new int[n][n];
        for(int i = 1; i <= num; i++) {

            if(c >= 0 && c < count) {
                arr[row - 1][x++] = i;
                c ++;
            }
            else if(c >= count  && c < count * 2 - 2) {
                arr[m++][n - row] = i;
                c ++;
            }else if(c >= count * 2 - 2 && c < count * 3 - 2) {
                arr[n - row][--x] = i;
                c ++;
            }else if(c >= count * 3 - 2 && c < count * 4 - 4){
                arr[--m][row - 1] = i;
                c ++;
            }
            if(c == count * 4 - 4) {
                count = n - 2 * row;
                row++;
                x++;
                m++;
                c = 0;
            }

        }
        return arr;
    }
}

编辑于 2020-04-22 12:00:34 回复(0)

Java

key、L

觉得好看的请点赞

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int num = 1;
        int rowBegin = 0, rowEnd = n - 1;
        int colBegin = 0, colEnd = n - 1;
        while(rowBegin <= rowEnd && colBegin <= colEnd)
        {
            for(int i = rowBegin; i <= rowEnd; i++)
            {
                result[rowBegin][i] = num;
                num ++;
            }
            rowBegin ++;
            for(int i = rowBegin; i <= rowEnd; i++)
            {
                result[i][colEnd] = num;
                num ++;
            }
            colEnd --;
            for(int i = colEnd; i >= colBegin; i--)
            {
                result[rowEnd][i] = num;
                num ++;
            }
            rowEnd --;
            for (int i = rowEnd; i >= rowBegin; i--) {
                result[i][colBegin] = num;
                num ++;
            }
            colBegin ++;
        }
        return result;
    }
}

发表于 2020-01-07 21:20:49 回复(0)

Java

HW柯可

public class Solution {
    public int[][] generateMatrix(int n) {
        if(n < 0)
            return null;
        int[][] matrix = new int[n][n];
        int left = 0, right = n - 1;
        int up = 0, down = n - 1;
        int count = 0;
        //动态修改上下左右边界，并同时判断是否越界
        while(true){
            for(int i = left; i <= right; i++){
               matrix[up][i] = ++count;  
            }
            up++;
            if(up > down) break;
            for(int i = up; i <= down; i++){
               matrix[i][right] = ++count;
            }
            right--;
            if(right < left) break;
            for(int i = right; i >= left; i--){
               matrix[down][i] = ++count;
            }
            down--;
            if(up > down) break;
            for(int i = down; i >= up; i--){
                matrix[i][left] = ++count;
           }
           left++;
           if(right < left) break;
        }
        return matrix;
    }
}

编辑于 2020-06-23 22:56:30 回复(0)

Java

放学后我不走~

最外圈开始，一圈一圈绕，代码如下：

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] a = new int[n][n];
        if(n==0)
            return a;
        int now = 1;
        int r,c;
        for(int i=0;i<(n+1)/2;i++){
            for(c=i;c<n-i;c++)
                a[i][c]=now++;
            c--;
            for(r=i+1;r<n-i;r++)    a[r][c]=now++;
            r--;             
      for(c--;c>=i;c--)                 
      a[r][c]=now++;             
      c++;
            for(r--;r>i;r--)                 
      a[r][c]=now++;             
      r++;         
      }
    return a;
    }

}

编辑于 2018-09-02 17:31:25 回复(1)

Java

forcht

/**

Created by forcht on 2018/5/21.
*/
public class Solution {
public int[][] generateMatrix(int n) {

int[][] p=new int[n][n];
 int x=0,y=0,i=1;
 int[] dx={0,1,0,-1};
 int[] dy={1,0,-1,0};
 int row=0,column=0;
 while (i<=n*n){
     while (row<n&&row>=0&&column<n&&column>=0&&p[row][column]==0){
         p[row][column]=i++;
         row+=dx[x];
         column+=dy[y];
     }
     row-=dx[x];
     column-=dy[y];
     x=(x+1)%4;
     y=(y+1)%4;
     row+=dx[x];
     column+=dy[y];
 }
 return p;

}

编辑于 2018-05-22 20:12:01 回复(0)

Java

Holiday_12138

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int left = 0, top = 0, right = n-1, bottom = n-1;
        int num = 0;
        while(top <= bottom && left <= right) {
            for(int i=left; i <= right && top <= bottom; i++) {
                matrix[top][i] = ++num;
            }
            top++;
            for(int i=top; i <= bottom && left <= right; i++) {
                matrix[i][right] = ++num;
            }
            right--;
            for(int i=right; i >= left && top <= bottom; i--) {
                matrix[bottom][i] = ++num;
            }
            bottom--;
            for(int i=bottom; i >= top && left <= right; i--) {
                matrix[i][left] = ++num;
            }
            left++;
        }
        return matrix;
    }
}

发表于 2017-06-20 13:51:02 回复(0)

Java

城市里的养猫者

This is my solution for Spiral Matrix I, https://oj.leetcode.com/discuss/12228/super-simple-and-easy-to-understand-solution. If you can understand that, this one is a no brainer :)

Guess what? I just made several lines of change (with comment "//change") from that and I have the following AC code:

public class Solution {
    public int[][] generateMatrix(int n) { // Declaration int[][] matrix = new int[n][n]; // Edge Case if (n == 0) { return matrix;
        } // Normal Case int rowStart = 0; int rowEnd = n-1; int colStart = 0; int colEnd = n-1; int num = 1; //change while (rowStart <= rowEnd && colStart <= colEnd) { for (int i = colStart; i <= colEnd; i ++) {
                matrix[rowStart][i] = num ++; //change }
            rowStart ++; for (int i = rowStart; i <= rowEnd; i ++) {
                matrix[i][colEnd] = num ++; //change }
            colEnd --; for (int i = colEnd; i >= colStart; i --) { if (rowStart <= rowEnd)
                    matrix[rowEnd][i] = num ++; //change }
            rowEnd --; for (int i = rowEnd; i >= rowStart; i --) { if (colStart <= colEnd)
                    matrix[i][colStart] = num ++; //change }
            colStart ++;
        } return matrix;
    }
}

Obviously, you could merge colStart and colEnd into rowStart and rowEnd because it is a square matrix. But this is easily extensible to matrices that are m*n.

发表于 2017-03-12 12:30:08 回复(0)

Java

詆調壹點

public class Solution {
   public int[][] generateMatrix(int n) {
		int[][] m = new int[n][n];
		int value = 1;
		for (int round = 0; round < n / 2 + n % 2; round ++ ) {
			for (int i = round; i < n - round; i ++ ) m[round][i] = value ++ ;
			for (int i = round + 1; i < n - round; i ++ ) m[i][n - round - 1] = value ++ ;
			for (int i = n - round - 2; i >= round; i -- ) m[n - round - 1][i] = value ++ ;
			for (int i = n - round - 2; i >= round + 1; i -- ) m[i][round] = value ++ ;
		}
		return m;
	}
}

发表于 2016-11-06 16:33:34 回复(0)