旋轉(zhuǎn)圖像

題目鏈接

---

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

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

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

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

• 結(jié)論：

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

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

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

實現(xiàn)代碼

void rotate(int** matrix, int matrixSize, int* matrixColSize){int n = matrixSize;//創(chuàng)建臨時數(shù)組int **ret = (int**)malloc(sizeof(int*) * (n));for (int i = 0; i < n; i++)ret[i] = (int*)malloc(sizeof(int) * n);//先儲存旋轉(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];//實現(xiàn)覆蓋for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)matrix[i][j] = ret[i][j];//釋放臨時數(shù)組的空間free(ret);
}

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

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

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

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

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

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

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

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

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

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

實現(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ū)域的每個元素為起點，依次進行旋轉(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;}}
}