微信公眾號：[每天曬白牙]
關注可了解更多的編程知識。問題或建議，請公眾號留言;
如果你覺文章對你有幫助，歡迎關注與
給你一幅由 N × N 矩陣表示的圖像，其中每個像素的大小為 4 字節。請你設計一種算法，將圖像旋轉 90 度。
不佔用額外內存空間能否做到？
https://leetcode-cn.com/problems/rotate-matrix-lcci/
示例示例 1給定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋轉輸入矩陣，使其變為:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
給定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋轉輸入矩陣，使其變為:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
按行旋轉，找旋轉前和旋轉後元素的坐標對應關係
原始矩陣
1 2 3
4 5 6
7 8 9
把第一行順時針旋轉 90 度後為：
x x 1
x x 2
x x 3
對應的坐標關係如下所示：
1:(0,0) -> (0,2)
2:(0,1) -> (1,2)
3:(0,2) -> (2,2)
把第二行順時針旋轉 90 度後為：
x 4 1
x 5 2
x 6 3
對應的坐標關係如下所示：
4:(1,0) -> (0,1)
5:(1,1) -> (1,1)
6:(1,2) -> (2,1)
第三行也類似，就不一一列出了，通過旋轉前和旋轉後坐標的對比，我們可以得出一個很重要的規律
旋轉前元素的坐標：(row,col)
旋轉後元素的坐標：(col,n-row-1)
matrix[row] [col] = matrix[col] [n-row-1]
這個規律很重要，下面方法也會用到
方法就很簡單了，我們遍歷矩陣，根據上面得出的旋轉前後的對應關係，把元素放到新的位置上，這裡我們用額外矩陣來存放旋轉後的元素，然後在最後把新矩陣複製到之前的矩陣中
源碼public static void rotate(int[][] matrix) {
int n = matrix.length;
if (n == 0) {
return;
}
// 新建一個矩陣用來存放旋轉後的元素
int[][] newMatrix = new int[n][matrix[0].length];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 根據旋轉前後的對應關係把元素放到要旋轉的位置上
newMatrix[j][n - i - 1] = matrix[i][j];
}
}
// 把存放旋轉後元素的矩陣複製到原先的矩陣上
System.arraycopy(newMatrix, 0, matrix, 0, newMatrix.length);
}
時間複雜度：O(n^2)
空間複雜度：O(n^2)
方法 1 佔用了額外的內存空間，其實這道題是可以不額外佔用空間也能實現，我們一起來看下下面的方法吧
方法 2：原地進行旋轉操作如果不藉助額外數組該怎麼操作？
在方法 1 中我們找到了規律是元素 matrix[row] [col] 旋轉到了 matrix[col] [n-row-1] ，如果不藉助額外數組，matrix[col] [n-row-1] 就會被覆蓋，所以需要先把 matrix[col] [n-row-1] 臨時存起來，下面就一起分析下不藉助額外數組進行原地旋轉吧，分析過程比較枯燥，建議自己嘗試一下，省的跟丟
temp = matrix[col] [n-row-1]
matrix[col] [n-row-1] = matrix[row] [col]
matrix[row] [col] = matrix[col] [n-row-1]
這裡需要注意的是新的 row = col；col = n-row-1，將其代入上面的規律中後為
matrix[n - row -1] [n - col -1] = matrix[col] [n - row -1]
可知，matrix[col] [n - row -1] 旋轉後的位置是 matrix[n - row -1] [n - col -1]，這個位置也會被覆蓋，所以還需要用 temp 做中轉
temp = matrix[n - row -1] [n - col -1]
matrix[n - row- 1] [n - col-1] = matrix[col] [n - row -1]
matrix[col] [n-row-1] = matrix[row] [col]
matrix[row] [col] = matrix[col] [n-row-1]
這裡需要注意的是新的 row = n - row -1；col = n - col -1，將其代入上面的規律中後為
matrix[n - col - 1] [row] = matrix[col] [n - row -1]
可知，matrix[n - row -1] [n - col -1] 旋轉後的位置為 matrix[n - col - 1] [row] ，但這個位置也會被覆蓋，依然需要用 temp 做中轉
temp = matrix[n - col - 1] [row]
matrix[n - col - 1] [row] = matrix[n - row -1] [n - col -1]
matrix[n - row -1] [n - col -1] = matrix[col] [n - row -1]
matrix[col] [n - row -1] = matrix[row] [col]
matrix[row] [col] = matrix[col] [n-row-1]
這裡需要注意的是新的 row = n - col - 1；col =row ，將其代入上面的規律中後為
matrix[row] [col] = matrix[n - col - 1] [row]
這次竟然發現了新大陸，matrix[col] [n - row -1] 旋轉後的位置為 matrix[row] [col]，最後又回到了起點
此刻腦子裡飄來了《那些年，我們一起追過的女孩》中的歌詞「又回到最初的起點，呆呆的站在鏡子前……」
綜合上面的推導，我們發現旋轉的重點就是下面的 4 個元素是處於一個循環中的
matrix[row] [col]
matrix[col] [n - row -1]
matrix[n - row - 1] [n - col - 1]
matrix[n - col - 1] [row]
對於上面 4 個元素的交換，我們用一個 temp 就可以實現了。但還有一點需要我們思考，就是要枚舉哪些位置的元素來進行原地交換，能保證不重不漏呢？因為一次原地交換需要 4 個元素參加。我們把 n 分為偶數和奇數來看
當 n 為偶數時，需要枚舉 (n/2)*(n/2) = n^2/4 個位置，所以矩陣左上角的子矩陣就符合我們的要求，可以做到不重不漏
下面用 n = 4 來舉個慄子，* 代表要枚舉的位置
n為偶數枚舉的位置當 n 為奇數時，矩陣的中心位置是不動的，只需要枚舉 ((n-1)/2)*((n+1)/2) = (n^2 -1/4) 個位置，矩陣的左上角的子矩陣還是符合要求的，可以做到不重不漏
下面以 n = 5 來舉個慄子，* 代表要枚舉的位置，x 代表中心位置
n為奇數枚舉的位置綜上，我們只需要枚舉矩陣左上角高為 n/2，寬為 (n+1)/2 的小矩陣就好了，就可以做到不重不漏
源碼public static void rotate2(int[][] matrix) {
int n = matrix.length;
if (n == 0) {
return;
}
for (int row = 0; row < n / 2; row++) {
for (int col = 0; col < (n + 1) / 2; col++) {
// 把 4 個位置的元素互換，注意順序
int temp = matrix[n - col -1][row];
matrix[n - col -1][row] = matrix[n - row -1][n - col -1];
matrix[n - row -1][n - col -1] = matrix[col][n-row-1];
matrix[col][n-row-1] = matrix[row][col];
matrix[row][col] = temp;
}
}
}
時間複雜度：O(n^2)
空間複雜度：O(1)，這個方法沒有額外使用空間
方法 2 的難點是找到 4 個元素位置的坐標關係，然後找到可以枚舉的不重不漏的子矩陣，方法已經很優秀了，但是廣大技術友總是能找到更牛逼的方法，下面的方法是從數學的角度來做到矩陣的原地旋轉
方法 3 ：原地雙百主要思想是用翻轉代替旋轉，先以對角線為軸，進行翻轉。再以每一行的中點為軸，進行翻轉。
我們通過示例圖來看下這個過程
對於原始矩陣，先以對角線為軸，進行翻轉
以對角線為軸進行翻轉翻轉完後如下所示：
以對角線為軸翻轉後然後對每一行以中點為軸，進行翻轉，效果如下：
以中點為軸翻轉後以對角線進行翻轉時，我們只需要枚舉對角線上方的元素，然後和下方元素進行交換，坐標對應關係如下
matrix[row] [col] --> matrix[col] [row]
對每行以中點進行翻轉時，我們只需要枚舉中點左邊的元素，然後和右邊的元素進行交換，坐標對應關係如下
matrix[row] [col] --> matrix[row] [n - col - 1]
源碼public static void rotate3(int[][] matrix) {
int n = matrix.length;
if (n == 0) {
return;
}
// 以對角線進行翻轉
for (int row = 0; row < n; row++) {
for (int col = row + 1; col < n; col++) {
int temp = matrix[col][row];
matrix[col][row] = matrix[row][col];
matrix[row][col] = temp;
}
}
// 對每一行以中點進行翻轉
for (int row = 0; row < n; row++) {
for (int col = 0; col < n / 2; col++) {
int temp = matrix[row][n - col - 1];
matrix[row][n - col - 1] = matrix[row][col];
matrix[row][col] = temp;
}
}
}
這種方法很巧妙，一般很難想到，所以只要你多刷肯定能學到一些比較好的方法，這種方法就是你看到過，你就會，沒看到過，可能就需要好好想想了，最終還不一定能想到
但這個方法還可以優化，可以把按對角線翻轉按中點翻轉放到一個大 for 循環下
源碼public static void rotate4(int[][] matrix) {
int n = matrix.length;
if (n == 0) {
return;
}
for (int row = 0; row < n; row++) {
// 以對角線進行翻轉
for (int col = row + 1; col < n; col++) {
int temp = matrix[col][row];
matrix[col][row] = matrix[row][col];
matrix[row][col] = temp;
}
// 對每一行以中點進行翻轉
for (int col = 0; col < n / 2; col++) {
int temp = matrix[row][n - col - 1];
matrix[row][n - col - 1] = matrix[row][col];
matrix[row][col] = temp;
}
}
}
時間複雜度：O(n^2)
空間複雜度：O(1) 沒有使用額外的空間
用過該題做過面試題的公司使用該題的公司其實有技術友分享過陌陌公司去年使用過這道題作為筆試題，不知道今年還有沒有，遇到的小夥伴可以留言說下
陌陌真題-技術友分享