目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
給定一個
n
×
n
n × n
n×n 的二維矩陣 matrix 表示一個影像，請你將影像順時針旋轉 90 度，
你必須在 原地 旋轉影像，這意味著你需要直接修改輸入的二維矩陣，請不要 使用另一個矩陣來旋轉影像，
示例 1：
![[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-DpPBiZ1s-1627210819425)(力扣500題刷題筆記.assets/mat1.jpg)]](https://img.uj5u.com/2021/07/27/250139270726541.png)
輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
![[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-RZPJVmNy-1627210819427)(力扣500題刷題筆記.assets/mat2.jpg)]](https://img.uj5u.com/2021/07/27/250139270726542.png)
輸入：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]]
示例 3：
輸入：matrix = [[1]]
輸出：[[1]]
示例 4：
輸入：matrix = [[1,2],[3,4]]
輸出：[[3,1],[4,2]]
提示：
matrix.length == nmatrix[i].length == n1 <= n <= 20-1000 <= matrix[i][j] <= 1000
2、思路
(操作分解) O ( n 2 ) O(n^2) O(n2)
我們對觀察樣例，找規律發現：先以左上-右下對角條線為軸做翻轉，再以中心的豎線為軸做翻轉，就可以翻轉90度，
因此可以得出一個結論，順時針90度應該是左上/右下對角線翻轉+左右翻轉，或者右上/左下對角線翻轉+上下翻轉，
程序如下：
- 先以左上-右下對角條線為軸做翻轉；
- 再以中心的豎線為軸做翻轉；
時間復雜度： O ( n 2 ) O(n^2) O(n2)， 額外空間： O ( 1 ) O(1) O(1)
3、c++代碼
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
//先沿斜對角線翻轉
int n = matrix.size();
for(int i = 0; i < n; i++)
for(int j = 0; j < i; j++)
swap(matrix[i][j],matrix[j][i]);
//再沿垂直豎線翻轉
for(int i = 0;i < n; i++)
for(int j = 0, k = n - 1; j < k ; j++, k--) //類似于雙指標，由兩端向中心靠齊
swap(matrix[i][j],matrix[i][k]);
}
};
4、java代碼
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
//先沿斜對角線翻轉
for(int i = 0;i < n;i ++)
for(int j = 0;j < i;j ++){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
//再沿垂直豎線翻轉
for(int i = 0;i < n;i ++)
for(int j = 0, k = n - 1; j < k ; j++, k--){
int temp = matrix[i][k];
matrix[i][k] = matrix[i][j];
matrix[i][j] = temp;
}
}
}
原題鏈接： 48. 旋轉影像
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/290252.html
標籤：java