卖萌的弱渣

I am stupid, I am hungry.

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example

Given n = 3,

You should return the following matrix:

1
2
3
4
5

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

Solution

  • Java: Best Solution
(Spiral-Matrix2.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ret = new int[n][n];
        int i=0; int j=0;

        int di=0; int dj=1;
        for(int k=0;k<n*n;k++){
            ret[i][j] = k+1;
            if(i+di <0 || j+dj < 0 || ret[(i+di)%n][(j+dj)%n]!=0){
                int tmp = di;
                di = dj;
                dj = -tmp;
            }
            i += di;
            j += dj;

        }
        return ret;
    }
}
  • Ideas is posted in Spiral Matrix
(Spiral-Matrix2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        if n == 0:
            return []
        if n == 1:
            return [[1]]
        ret = [[0]*n for i in range(n)]
        direct = 0 # 0: go right, 1: go down, 2: go left, 3: got up

        l = 0
        r = n-1
        u = 0
        d = n-1
        num = 1

        while l<=d and u <= d:
            if direct ==0:
                for i in range(l,r+1):
                    ret[u][i] = num
                    num += 1
                u += 1
                direct = 1
            elif direct == 1:
                for i in range(u,d+1):
                    ret[i][r] = num
                    num += 1
                r -= 1
                direct = 2
            elif direct == 2:
                for i in range(r,l-1,-1):
                    ret[d][i] = num
                    num += 1
                d -= 1
                direct = 3
            else: # direct == 3
                for i in range(d,u-1,-1):
                    ret[i][l] = num
                    num += 1
                l += 1
                direct = 0
        return ret