当前位置:网站首页>Leetcode 48 rotating image

Leetcode 48 rotating image

2020-11-09 19:10:55 Want to exchange steamed stuffed bun for thesis

LeetCode48 Rotated image

Title Description

Given a n × n Two dimensional matrix representation of an image .

Rotate image clockwise 90 degree .

Be careful : Change it in place

Examples

 Given  matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

 In situ rotation input matrix , Turn it into :
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
 Given  matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

 In situ rotation input matrix , Turn it into :
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Algorithm analysis

  • Flip diagonally
  • Flip on the center axis
1 2 3
4 5 6
7 8 9

====  Diagonals 
1 4 7
2 5 8
3 6 9

====  Central axis 
7 4 1
8 5 2
9 6 3

Time complexity

\(O(n^{2})\)

Java Code

class Solution {
    static void swap(int[][] matrix, int x1, int y1, int x2, int y2){
        int t = matrix[x1][y1];
        matrix[x1][y1] = matrix[x2][y2];
        matrix[x2][y2] = t;
    }
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i = 0; i < n; i++){
            for(int j = 0;j<=i;j++){
                swap(matrix,i,j,j,i);
            }
        }

        for(int i = 0;i<n;i++){
            for(int j = 0;j<n/2;j++){
                swap(matrix,i,j,i,n-j-1);
            }
        }

    }
}

版权声明
本文为[Want to exchange steamed stuffed bun for thesis]所创,转载请带上原文链接,感谢