題目敘述
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n**2 in spiral order.
Example 1:
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Example 2:
Input: n = 1
Output: [[1]]
Constraints:
題目翻譯
題目的需求很簡單就是會給一個整數參數 n，然後從數字 1 開始從外而內做順時針的螺旋排列。
解法解析
這題的解法有以下幾種方式：
- 依照題目所說的從外而內的螺旋排列
- 由內而外的排序，可以參考討論區的部分
其實主要就是判斷這個邊界索引的邏輯，有幾種方式：
- 用四個變數紀錄四個方向的索引，如 Go 的第二個範例
- 直接用計算的方式處理，優化的方式是使用取模。如 JavaScript 和 Python 的第二個範例
解法範例
Go
Traverse Layer
func generateMatrix(n int) [][]int {
result := make([][]int, n)
for i := range result {
result[i] = make([]int, n)
}
var cnt int = 1
for layer := 0; layer < (n+1)/2; layer++ {
for i := layer; i < n-layer; i++ {
result[layer][i] = cnt
cnt++
}
for i := layer + 1; i < n-layer; i++ {
result[i][n-layer-1] = cnt
cnt++
}
for i := n - layer - 2; i >= layer; i-- {
result[n-layer-1][i] = cnt
cnt++
}
for i := n - layer - 2; i > layer; i-- {
result[i][layer] = cnt
cnt++
}
}
return result
}
Traverse Layer for 4 directino
func generateMatrix(n int) [][]int {
if n == 0 {
return [][]int{}
}
result := make([][]int, n)
for i := range result {
result[i] = make([]int, n)
}
var top, bottom, left, right int = 0, n - 1, 0, n - 1
var cnt, layerRange int = 1, n * n
for cnt <= layerRange {
for i := left; i <= right && cnt <= layerRange; i++ {
result[top][i] = cnt
cnt++
}
top++
for i := top; i <= bottom && cnt <= layerRange; i++ {
result[i][right] = cnt
cnt++
}
right--
for i := right; i >= left && cnt <= layerRange; i-- {
result[bottom][i] = cnt
cnt++
}
bottom--
for i := bottom; i >= top && cnt <= layerRange; i-- {
result[i][left] = cnt
cnt++
}
left++
}
return result
}
JavaScript
Traverse Layer
var generateMatrix = function (n) {
const result = new Array(n).fill(0).map(() => new Array(n).fill(0));
let cnt = 1;
for (let layer = 0; layer < Math.floor((n + 1) / 2); layer++) {
for (let i = layer; i < n - layer; i++) {
result[layer][i] = cnt++;
}
for (let i = layer + 1; i < n - layer; i++) {
result[i][n - layer - 1] = cnt++;
}
for (let i = layer + 1; i < n - layer; i++) {
result[n - layer - 1][n - i - 1] = cnt++;
}
for (let i = layer + 1; i < n - layer - 1; i++) {
result[n - i - 1][layer] = cnt++;
}
}
return result;
};
Optimized spiral traversal
var generateMatrix = function (n) {
const result = [...Array(n)].map(() => Array(n).fill(0));
const dir = [
[0, 1],
[1, 0],
[0, -1],
[-1, 0],
];
let row = 0,
col = 0,
d = 0,
cnt = 1;
while (cnt <= n * n) {
result[row][col] = cnt++;
let r = (row + dir[d][0]) % n;
let c = (col + dir[d][1]) % n;
if (result[r][c] !== 0) {
d = (d + 1) % 4;
}
row += dir[d][0];
col += dir[d][1];
}
return result;
};
Kotlin
PHP
Python
Traverse Layer
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
result = [[0 for _ in range(n)] for _ in range(n)]
cnt = 1
for layer in range((n + 1) // 2):
for i in range(layer, n - layer):
result[layer][i] = cnt
cnt += 1
for i in range(layer + 1, n - layer):
result[i][n - layer - 1] = cnt
cnt += 1
for i in range(layer + 1, n - layer):
result[n - layer - 1][n - i - 1] = cnt
cnt += 1
for i in range(layer + 1, n - layer - 1):
result[n - i - 1][layer] = cnt
cnt += 1
return result
Optimized spiral traversal
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
result = [[0 for _ in range(n)] for _ in range(n)]
dr = [[0, 1], [1, 0], [0, -1], [-1, 0]]
row, col, d, cnt = 0, 0, 0, 1
while cnt <= n * n:
result[row][col] = cnt
r = (row + dr[d][0]) % n
c = (col + dr[d][1]) % n
if result[r][c] != 0:
d = (d + 1) % 4
row += dr[d][0]
col += dr[d][1]
cnt += 1
return result
Rust
Swift