未分類

Rotate Image

Array, Go, LeetCode

Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

提示 解題應用
Array Array/Slice

Default:

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

解答思路:

很久以前曾解過一樣的題目，沒想到還會再次碰上，一開始還壓根忘了如何去旋轉二元陣列，實際上是有小技巧的，如果是順時針旋轉就先將前後橫排對換，例如第一橫排與最後一橫排位置互換，第二橫排與倒數第二橫排互換，而如果是逆時針則是將左右直列對換，接下來不論是順時針還是逆時針以對角線(左上到右下)為中心將兩兩對稱到的值互換，如此一來便完成了90度角的旋轉。

1
2
3
4
1234          $%^&          $~51
5678    =>    ~!@#    =>    %!62
~!@#          5678          ^@73
$%^&          1234          &#84

程式碼解說:

因為本題要做順時針旋轉，所以一開始就要先將前後橫排對掉，所以我們分別指向第一橫排與最後一橫排的位置，接著再以一回圈取出前排的每個元素來與後排的元素做交換以達成橫排位置的對掉，結束後原本指向前後橫排的位置再分別向內縮直到所有的橫排都對掉完畢為止(前排指向的位置大於等於後排指向的位置)

1
2
3
4
5
6
7
8
9
10
11
12
var tmp int
front := 0
rear := len(matrix) - 1
for front < rear {
	for i, v := range matrix[front] {
		tmp = v
		matrix[front][i] = matrix[rear][i]
		matrix[rear][i] = tmp
	}
	front++
	rear--
}

再來就是以對角線(左上到右下)為中心將兩兩對稱到的值互換，以下圖為例:

1
2
3
4
5
X123→
1X23→
22X3→
333X
↓↓↓

我們關注的是橫排的index(123,23,3)與直列的index(123,23,3)，了解到對角線將兩兩對稱值互換的規律後，接下來便能很容易的寫出對角線對稱交換的程式碼，這邊的i-1代表橫排的位置，而j則是表示直列的位置

1
2
3
4
5
6
7
for i := 1; i <= len(matrix)-1; i++ {
	for j := i; j <= len(matrix)-1; j++ {
		tmp = matrix[i-1][j]
		matrix[i-1][j] = matrix[j][i-1]
		matrix[j][i-1] = tmp
	}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func rotate(matrix [][]int) {
	var tmp int
	front := 0
	rear := len(matrix) - 1
	for front < rear {
		for i, v := range matrix[front] {
			tmp = v
			matrix[front][i] = matrix[rear][i]
			matrix[rear][i] = tmp
		}
		front++
		rear--
	}
	for i := 1; i <= len(matrix)-1; i++ {
		for j := i; j <= len(matrix)-1; j++ {
			tmp = matrix[i-1][j]
			matrix[i-1][j] = matrix[j][i-1]
			matrix[j][i-1] = tmp
		}
	}
}

總結:

要將一二元陣列做90度旋轉，如果是順時針旋轉就先將前後橫排對換，而如果是逆時針則是將左右直列對換，接下來不論是順時針還是逆時針以對角線(左上到右下)為中心將兩兩對稱到的值互換，如此一來便完成了90度角的旋轉。

分享到