Saturday, March 7, 2015

48. Rotate Image Leetcode Java

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
Solution:
It is not difficult to come out a solution. But it is a little bit tricky when do this in place.
We can treat the matrix as a layered structure. And we can rotate the image layer by layer.
For each layer, we process it pixel by pixel, we only need a temp variable to help the swap up->temp, left->up, bottom->left, right->bottom, temp->right;
Time complexity: O(n*n) space: O(1)
 public void rotate(int[][] matrix) {  
    if(matrix==null || matrix.length<=1 || matrix[0].length<=1) return;  
    int n=matrix.length;  
    int layer=0;  
    while(layer<n/2){  
      for(int i=layer;i<n-1-layer;i++){  
        int temp=matrix[layer][i];  
        matrix[layer][i]=matrix[n-1-i][layer];  
        matrix[n-1-i][layer]=matrix[n-1-layer][n-i-1];  
        matrix[n-1-layer][n-1-i]=matrix[i][n-1-layer];  
        matrix[i][n-1-layer]=temp;  
      }  
      layer++;  
    }  
    return;  
   }  

No comments:

Post a Comment