給你一幅由 N × N 矩陣表示的圖像榆鼠，其中每個(gè)像素的大小為 4 字節(jié)馍驯。請(qǐng)你設(shè)計(jì)一種算法，將圖像旋轉(zhuǎn) 90 度兑燥。
不占用額外內(nèi)存空間能否做到？
示例 1:
給定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋轉(zhuǎn)輸入矩陣琴拧，使其變?yōu)?
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
給定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋轉(zhuǎn)輸入矩陣，使其變?yōu)?
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
Solution:
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
size = len(matrix[0])
times = size
for i in range(times):
if times >= 2:
for j in range(i, times - 1):
tmp = matrix[i][j]
matrix[i][j] = matrix[size - j - 1][i]
matrix[size - j - 1][i] = matrix[size - i - 1][size - j - 1]
matrix[size - i - 1][size - j - 1] = matrix[j][size - i - 1]
matrix[j][size - i - 1] = tmp
times = times - 1
else:
break
解題思路：
這個(gè)題初拿到手嘱支，糾結(jié)了什么叫不用額外的內(nèi)存空間蚓胸，其實(shí)就是原地算法。一個(gè)原地算法（in-place algorithm）是一種使用小的除师，固定數(shù)量的額外之空間來(lái)轉(zhuǎn)換資料的算法沛膳。當(dāng)算法執(zhí)行時(shí)，輸入的資料通常會(huì)被要輸出的部分覆蓋掉汛聚。簡(jiǎn)而言之锹安，我理解的原地就是覆蓋原數(shù)據(jù)，而且你只能借助固定數(shù)量的額外空間倚舀，比如一個(gè)temp叹哭，而不是將數(shù)組放到一個(gè)新的變量里。下面是我先想到的用tmp輔助更新數(shù)據(jù)的思路痕貌。
-
找規(guī)律风罩，旋轉(zhuǎn)九十度，那么其實(shí)我們可以發(fā)現(xiàn)舵稠，經(jīng)過(guò)matrix[i][j]經(jīng)過(guò)旋轉(zhuǎn)超升，這個(gè)數(shù)字在第幾行就變到了倒數(shù)第幾列入宦，在第幾列就變到了第幾行，也就是
matrix[i][j] -> matrix[j][size - i - 1]室琢，拿幾個(gè)具體的例子看看乾闰，這里我在圖里舉例了四個(gè)角的變換，不難發(fā)現(xiàn)這個(gè)規(guī)律
image.png -
考慮怎么換呢盈滴，倆倆置換是不可能的涯肩，因?yàn)槲覀円呀?jīng)找到規(guī)律了，如果倆倆置換雹熬，那原來(lái)的數(shù)字會(huì)被替換掉宽菜，規(guī)律就不成立了，于是我們可以選擇四個(gè)四個(gè)的變竿报，因?yàn)槊克膫€(gè)變換都會(huì)是一個(gè)環(huán)铅乡，規(guī)律還是成立。（最后介紹了不會(huì)被替換的簡(jiǎn)便方法）
image.png -
下面考慮該怎么換呢烈菌，只用一個(gè)tmp我們可以一次將四個(gè)數(shù)字變換到位阵幸，意思跟冒泡排序差不多，但是這回得倒著推芽世，先把1給tmp挚赊，再把7給1，9給7济瓢，3給9荠割，最后把tmp給3。如上圖藍(lán)色的圓圈編號(hào)的順序操作旺矾，順序無(wú)所謂蔑鹦，懂怎么個(gè)流程就行了。這種旋轉(zhuǎn)屢試不爽
image.png 下面我們找需要旋轉(zhuǎn)多少次箕宙，怎么樣才結(jié)束呢嚎朽，看上圖，
當(dāng)size為3的時(shí)候柬帕，我只需要做一次外層的旋轉(zhuǎn)哟忍，且這個(gè)外層旋轉(zhuǎn)做了兩次(0,0)和(0,1)所在的兩個(gè)環(huán)。
當(dāng)size==4 的時(shí)候做了2層旋轉(zhuǎn)陷寝，最外面的那一層做了(0,0),(0,1)(0,2)環(huán)旋轉(zhuǎn),內(nèi)層做了(1,1)環(huán)旋轉(zhuǎn)
當(dāng)size==5的時(shí)候锅很，做了3層旋轉(zhuǎn)，最外面一層做了(0,0)(0,1)(0,2)(0,3),內(nèi)一層(1,1)(1,2)
可以發(fā)現(xiàn)盼铁，每往內(nèi)一層粗蔚，需要旋轉(zhuǎn)的正方形的邊長(zhǎng) - 2，直到最里面那層的正方形小于2饶火，也就是只剩1個(gè)或者沒(méi)有了就停止了旋轉(zhuǎn)了鹏控。
Note：
本來(lái)以為不用temp值會(huì)被替換掉致扯，后來(lái)嘗試了一下發(fā)現(xiàn)，python可以同時(shí)對(duì)多個(gè)值操的置換的時(shí)候不會(huì)被覆蓋当辐，所以把代碼更新了一下
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
size = len(matrix[0])
times = size
for i in range(times):
if times >= 2:
for j in range(i, times - 1):
matrix[i][j], matrix[size - j - 1][i], matrix[size - i - 1][size - j - 1], matrix[j][size - i - 1] = \
matrix[size - j - 1][i], matrix[size - i - 1][size - j - 1], matrix[j][size - i - 1], matrix[i][j]
# tmp = matrix[i][j]
# matrix[size - j - 1][i] = matrix[size - i - 1][size - j - 1]
# matrix[size - i - 1][size - j - 1] = matrix[j][size - i - 1]
# matrix[j][size - i - 1] = tmp
times = times - 1
else:
break
