Algorithm to Generate the Spiral Matrix in Clock-wise Order

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

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) —

推荐阅读：
“先填空，再列综合算式”总出错怎么办　 火车的钟声　 谷歌seo的内容素材和文章构思从哪里获取？（下篇）　 谷歌seo的内容素材和文章构思从哪里获取？（上篇）　 seo专家告诉你，新网站怎么做网站优化　 企业做Google SEO如何用内链优化来提高排名　 建网站赚钱注意事项 别怪我没提醒你　 自己建网站可以挣钱吗？做个人网站赚钱你必须要掌握的基础经验　 网站赚钱 有时候就是那么简单　 网上“复制”项目容易又免费 “粘贴”赚钱怎么那么简单　
评论列表
添加评论