未分類

Spiral Matrix

Array, Go, LeetCode

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example:

Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

提示 解題應用
Array 二元陣列

Default:

1
2
3
func spiralOrder(matrix [][]int) []int {
}

解答思路:

原本以圖形來思考是不是只要用一個變數就可以分別遍歷外圈、內圈，也就是說當遍歷最外圈時，四個邊內縮為0，要遍歷內圈一點四個邊就內縮1…等等，然而沒這麼簡單，因為還有重覆的問題，也就是說如果直接遍歷四個邊最後會造成四個角都出現重覆的值，當然可以每次到四個角的位置就篩選掉一次重覆的結果，但倒不如在遍歷的時候就避免會重覆如下的方式:

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
[初始值]
rowStart: 0
rowEnd  : m
colStart: 0
colEnd  : n
              colStart: 0
 (colStart++)      →              (rowStart++)
                colEnd: m
              - - - - - - - - - →
              ↑                 ∣ rowStart: 1
              |                 ∣      ↓
              |                 ∣   rowEnd: n
rowStart:   1 |                 ∣
      ↑       |                 ∣
  rowEnd: n-1 |                 ∣
              ← - - - - - - - - ↓
		              colEnd: m-1
	(rowEnd--)           ←         (colEnd--)
	               colStart:   0
[遍歷完最外圈後]
rowStart: 1
rowEnd  : m-1
colStart: 1
colEnd  : n-1

藉由四個變數來控制要遍歷的位置以避免重覆之外，最後當最外圈遍歷結束後，四個變數自然也就向內縮，所以只要一開始便想到要以四個變數來控制遍歷的位置，剩下的程式碼就很容易順勢寫出來了。

程式碼解說:

一開始先判斷二元陣列是否為空，如果是便直接回傳空陣列，接下來就是初始化四個變數來控制要遍歷的位置，橫排或直列的起始值皆為0，至於橫排的最終值是二元陣列的橫排有多少再扣1，而直列的最終值則是二元陣列中的每列有多少個元素再扣1，最後才開始螺旋遍歷二元陣列直到橫排或直列的起始值超過最終值才回傳結果陣列

1
2
3
4
5
6
7
8
9
10
11
12
var result []int
if len(matrix) == 0 {
	return result
}
var rowStart int
rowEnd := len(matrix) - 1
var colStart int
colEnd := len(matrix[0]) - 1
for colStart <= colEnd && rowStart <= rowEnd {
...
}
return result

一開始先遍歷最上面的邊，而待遍歷結束後就可以先將rowStart的值內縮(+1)

1
2
3
4
for i := colStart; i <= colEnd; i++ {
	result = append(result, matrix[rowStart][i])
}
rowStart++

接著便遍歷最右邊的邊，剛好rowStart的值內縮(+1)，所以可以避免右上角的值重覆，因此可以放心繼續遍歷，而待遍歷結束後就可以將colEnd的值內縮(-1)

1
2
3
4
for i := rowStart; i <= rowEnd; i++ {
	result = append(result, matrix[i][colEnd])
}
colEnd--

再來是遍歷最下面的邊，而也是因為colEnd的值內縮(-1)，可以避免右下角的值重覆以繼續遍歷，不過這次多了一層row範圍的判斷，原因在於這個二元陣列是矩形mxn而非正方形mxm，可能外層遍歷後內圈只剩一橫排的陣列，此時這一橫排的陣列可能被當作最上面的邊而早已被遍歷，所以這邊就要再多一層row範圍的判斷以確保該僅存橫排的陣列不會再次被當作最下面的邊而重覆遍歷，待遍歷結束後就可以將rowEnd的值內縮(-1)

1
2
3
4
5
6
if rowStart <= rowEnd {
	for i := colEnd; i >= colStart; i-- {
		result = append(result, matrix[rowEnd][i])
	}
}
rowEnd--

最後則是遍歷最左邊的邊，因為rowEnd的值內縮(-1)，可以避免左下角的值重覆以繼續遍歷，這邊一樣多了一層col範圍的判斷，僅存橫排的陣列可能已被當作最右邊的邊而被遍歷，所以多一層col範圍的判斷以確保不會再次被當作最左邊的邊而重覆遍歷，待遍歷結束後就可以將colStart的值內縮(+1)

1
2
3
4
5
6
if colStart <= colEnd {
	for i := rowEnd; i >= rowStart; i-- {
		result = append(result, matrix[i][colStart])
	}
}
colStart++

完整程式碼:

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
func spiralOrder(matrix [][]int) []int {
	var result []int
	if len(matrix) == 0 {
		return result
	}
	var rowStart int
	rowEnd := len(matrix) - 1
	var colStart int
	colEnd := len(matrix[0]) - 1
	for colStart <= colEnd && rowStart <= rowEnd {
		for i := colStart; i <= colEnd; i++ {
			result = append(result, matrix[rowStart][i])
		}
		rowStart++
		for i := rowStart; i <= rowEnd; i++ {
			result = append(result, matrix[i][colEnd])
		}
		colEnd--
		if rowStart <= rowEnd {
			for i := colEnd; i >= colStart; i-- {
				result = append(result, matrix[rowEnd][i])
			}
		}
		rowEnd--
		if colStart <= colEnd {
			for i := rowEnd; i >= rowStart; i-- {
				result = append(result, matrix[i][colStart])
			}
		}
		colStart++
	}
	return result
}

總結:

給一mxn的二元陣列，要以螺旋狀的方式來輸出結果，最重要的是要以四個變數來控制要遍歷的位置，分別是rowStart、rowEnd、colStart、colEnd，詳情可以參考解答思路的細節解說，總之只要一開始便想到要以四個變數來控制遍歷的位置，剩下的程式碼就很容易順勢寫出來了。

分享到