旋轉(zhuǎn)圖像

題目鏈接

---

方法一：利用輔助數(shù)組

通過對(duì)示例的觀察和分析，我們可以得到這樣的結(jié)論：

• 對(duì)于原數(shù)組的下標(biāo)為i行元素，順時(shí)針旋轉(zhuǎn)九十度后，都變成了下標(biāo)為（n-1-i）列元素。如圖所示：

• 對(duì)于原數(shù)組的下標(biāo)為j列元素，順時(shí)針旋轉(zhuǎn)九十度后，都變成了下標(biāo)為(j)行元素。如圖所示：

• 結(jié)論：

假設(shè)帶旋轉(zhuǎn)的元素位置為nums[i][j]，那么順時(shí)針旋轉(zhuǎn)九十度后這個(gè)元素的位置就應(yīng)該是nums[j][n-1-i]

這樣想清楚后這題似乎就變得十分簡(jiǎn)單，但是我們應(yīng)該想到旋轉(zhuǎn)玩一組數(shù)據(jù)后，有些數(shù)據(jù)就會(huì)被覆蓋，如圖：

因此，我們可以再新創(chuàng)建一個(gè)臨時(shí)數(shù)組來保存這些旋轉(zhuǎn)后的數(shù)據(jù)，然后再將新數(shù)組的數(shù)據(jù)覆蓋到原數(shù)組就可以了。

實(shí)現(xiàn)代碼

void rotate(int** matrix, int matrixSize, int* matrixColSize){int n = matrixSize;//創(chuàng)建臨時(shí)數(shù)組int **ret = (int**)malloc(sizeof(int*) * (n));for (int i = 0; i < n; i++)ret[i] = (int*)malloc(sizeof(int) * n);//先儲(chǔ)存旋轉(zhuǎn)后數(shù)組的數(shù)據(jù)for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)ret[j][n - 1 - i] = matrix[i][j];//實(shí)現(xiàn)覆蓋for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)matrix[i][j] = ret[i][j];//釋放臨時(shí)數(shù)組的空間free(ret);
}

方法二： 原地旋轉(zhuǎn)

我們先來看2 * 2數(shù)組順時(shí)針旋轉(zhuǎn)九十度的情形：

我們可以認(rèn)為旋轉(zhuǎn)過程是這樣的：D->A、C->D、B->C、A->B，應(yīng)該注意執(zhí)行完D->A后，數(shù)據(jù)A就被覆蓋了，因此我們需要?jiǎng)?chuàng)建一個(gè)臨時(shí)變量來保存數(shù)據(jù)A，這樣，這個(gè)旋轉(zhuǎn)過程就變?yōu)榱?code>temp=A, D->A、C->D、B->C、temp->B

我們將數(shù)組擴(kuò)大，那么由上面的推理可以得到，每經(jīng)過上面的一輪變換，都可以旋轉(zhuǎn)數(shù)組的4個(gè)元素：

那么如何將整個(gè)數(shù)組的元素都旋轉(zhuǎn)，我們只需要取數(shù)組左上角1/4的元素，并將這些數(shù)據(jù)作為旋轉(zhuǎn)起點(diǎn)，依次進(jìn)行旋轉(zhuǎn)即可：

同時(shí)經(jīng)過分析我們也可以得到，一輪旋轉(zhuǎn)的4個(gè)元素的下標(biāo)變化應(yīng)該是這樣的：

最后，我們應(yīng)該注意區(qū)分n為奇數(shù)或偶數(shù)的情況：

• 當(dāng)n為偶數(shù)，數(shù)組的旋轉(zhuǎn)起始位置（左上角1/4區(qū)域）為：

• 當(dāng)n為奇數(shù)，數(shù)組的旋轉(zhuǎn)起始位置（左上角1/4區(qū)域）為：

因此，當(dāng)n為奇數(shù)或者偶數(shù)時(shí)，區(qū)域的列數(shù)都為n/2。當(dāng)n為偶數(shù)時(shí)，行數(shù)為n/2，n為奇數(shù)時(shí)，行數(shù)為(n+1)/2

實(shí)現(xiàn)代碼

void rotate(int** matrix, int matrixSize, int* matrixColSize){int n = matrixSize;//確定左上角1/4區(qū)域的范圍int row = n / 2;int col = (n + 1) / 2;//以左上角1/4區(qū)域的每個(gè)元素為起點(diǎn)，依次進(jìn)行旋轉(zhuǎn)for (int i = 0; i < row; i++){for (int j = 0; j < col; j++){int temp = matrix[i][j];matrix[i][j] = matrix[n-1-j][i];matrix[n-1-j][i] = matrix[n-1-i][n-1-j];matrix[n-1-i][n-1-j] = matrix[j][n-1-i];matrix[j][n-1-i] = temp;}}
}