Algorithm to Generate the Spiral Matrix in Clock-wise Order

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

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

推荐阅读：
WordPress定时发布功能 网站SEO优化的好帮手　 robots.txt的格式、写法及其对于WordPress的seo作用　 无需修改代码 轻松隐藏WordPress管理工具栏　 修改WordPress标签云字体大小及标签显示数量的方法　 巧用wordpress更新服务 提升搜索引擎收录文章的速度　 无需登陆FTP 新建一个wordpress主题文件　 wordpress响应式杂志主题—Semicolon　 禁止wordpress仪表盘加载谷歌字体链接　 通过wordpress仪表盘修改wp_options数据表　 荆州古城作文400字　
评论列表
添加评论