【問題描述】 [面試題 01.07. 旋轉矩陣]

示例 1:給定 matrix = [[1,2,3],[4,5,6],[7,8,9] ],原地旋轉輸入矩陣，使其變為: [[7,4,1],[8,5,2],[9,6,3] ]給你一幅由 N × N 矩陣表示的圖像，其中每個像素的大小為 4 字節。請你設計一種算法，將圖像旋轉 90 度。不占用額外內存空間能否做到？

【解答思路】

1. 借助輔助矩陣 找規律 （不符合題意）

時間復雜度：O(N^2) 空間復雜度：O(N)

public void rotate1(int[][] matrix) {if (matrix == null || matrix.length == 0) return;int n = matrix.length;int[][] res = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {res[j][n-i-1] = matrix[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix[i][j] = res[i][j];}}}

2.先沿對角線翻轉 ，再沿中間列翻轉

時間復雜度：O(N^2) 空間復雜度：O(1)

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;//矩陣轉置，即按斜對角線進行數據交換for(int i=0;i<n;i++){for(int j=i;j<n;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;j<n/2;j++){int temp = matrix[i][j];matrix[i][j] = matrix[i][n-j-1];matrix[i][n-j-1] = temp;}}} }

3. 原地修改，原矩陣分塊交換 四個一組 交換位置

時間復雜度：O(N^2) 空間復雜度：O(1)

public void rotate2(int[][] matrix) {if (matrix == null || matrix.length == 0) return;int n = matrix.length;for (int i = 0; i < n / 2 ; i++) {for (int j = 0; j < (n + 1) / 2; j++) {int tmp = matrix[i][j];matrix[i][j] = matrix[n-j-1][i];matrix[n-j-1][i] = matrix[n-i-1][n-j-1];matrix[n-i-1][n-j-1] = matrix[j][n-i-1];matrix[j][n-i-1] = tmp;}}}

【總結】

翻轉數組 找規律

分塊分治思想 對折思想

優化思想 空間時間互換

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][面试题 01.07][找规律][旋转数组]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。