Algorithm to Generate the Spiral Matrix in Clock-wise Order

  • 时间：2020-09-12 10:06:27
  • 分类：网络文摘
  • 阅读：162 次

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

Example:
Input: 3

Output:

1
2
3
4
5

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

Walk and Turn Algorithm to Fill the Matrix in Sprial Clock-wise Order

We start at the top-left corner where we fill number 1, then the initial direction is RIGHT, then we keep walking until we hit the border or the cell has been filled already. Then we turn right, repeatedly doing this until we have finished the matrix.

The special case is the 1×1 matrix, we can just immediately return [1] without walking. The following is the Java implementation of the Clock-wise spiral matrix. In Java, we use Arrays.fill to initialize a one-dimension array. We can use a for loop to initialize a two dimensional array using Arrays.fill.

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

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        for (int[] x: res) {
            Arrays.fill(x, -1);
        }
        if (n <= 1) {
            res[0][0] = 1;
            return res;
        }
        int d[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, r = 0, c = 0, num = 1;
        int total = n * n;
        res[0][0] = 1;
        while (num < total) {
            int nr = r + d[x][0];
            int nc = c + d[x][1];
            if (nr >= n || nc >= n || nr < 0 || nc < 0 || res[nr][nc] != -1) {
                x = (x + 1) % 4;
            } else {
                r = nr;
                c = nc;
                res[r][c] = ++ num;
            }
        }
        return res;        
    }
}
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        for (int[] x: res) {
            Arrays.fill(x, -1);
        }
        if (n <= 1) {
            res[0][0] = 1;
            return res;
        }
        int d[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, r = 0, c = 0, num = 1;
        int total = n * n;
        res[0][0] = 1;
        while (num < total) {
            int nr = r + d[x][0];
            int nc = c + d[x][1];
            if (nr >= n || nc >= n || nr < 0 || nc < 0 || res[nr][nc] != -1) {
                x = (x + 1) % 4;
            } else {
                r = nr;
                c = nc;
                res[r][c] = ++ num;
            }
        }
        return res;        
    }
}

Similarly, the following is the C++ version of the Spiral square matrix.

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

class Solution {
public:
    vector<vector>int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, -1));
        if (n <= 1) {
            return vector<vector<int>>(1, {1});
        }
        int d[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, r = 0, c = 0, num = 1;
        int total = n * n;
        res[0][0] = 1;
        while (num < total) {
            int nr = r + d[x][0];
            int nc = c + d[x][1];
            if (nr >= n || nc >= n || nr < 0 || nc < 0 || res[nr][nc] != -1) {
                x = (x + 1) % 4;
            } else {
                r = nr;
                c = nc;
                res[r][c] = ++ num;
            }
        }
        return res;
    }
};
class Solution {
public:
    vector<vector>int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, -1));
        if (n <= 1) {
            return vector<vector<int>>(1, {1});
        }
        int d[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, r = 0, c = 0, num = 1;
        int total = n * n;
        res[0][0] = 1;
        while (num < total) {
            int nr = r + d[x][0];
            int nc = c + d[x][1];
            if (nr >= n || nc >= n || nr < 0 || nc < 0 || res[nr][nc] != -1) {
                x = (x + 1) % 4;
            } else {
                r = nr;
                c = nc;
                res[r][c] = ++ num;
            }
        }
        return res;
    }
};

Syntaxally much the same, both implementations run O(N^2) time and space complexity.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
中秋节的夜晚_关于中秋赏月的小学生作文400字　 六一儿童节的记忆作文　 中国教师节献给老师的礼物作文800字　 关于元旦节的作文600字　 家乡的上灯节作文　 欢乐的火把节_描写少数民族节日的小学生作文800字　 欢欢喜喜闹元宵_关于描写元宵佳节的小学生作文350字　 元旦节的作文300字　 令人难忘的中秋节作文　 古埃及分数　
评论列表
添加评论