Friday, January 2, 2015

Rotate Image (LeetCode Array)

Question: 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?

Idea: First flip the matrix by the counter-diagonal i+j=n-1, where matrix[i][j]. Then reverse each column. The result is to rotate 90 degrees clockwise.

Time: O(n) Space: O(1)

Code: 
 public class Solution {  
   public void rotate(int[][] matrix) {  
     int n=matrix.length;  
     for(int i=0;i<n;i++)  
       for(int j=0;j<n-1-i;j++)  
         swap(matrix,i,j,n-1-j,n-1-i);  
     for(int j=0;j<n;j++)  
       for(int i=0;i<n/2;i++)  
         swap(matrix,i,j,n-1-i,j);  
   }  
   public void swap(int[][] matrix, int x1, int y1,int x2,int y2)  
   {  
     int tmp=matrix[x1][y1];  
     matrix[x1][y1]=matrix[x2][y2];  
     matrix[x2][y2]=tmp;  
   }  
 }  

No comments:

Post a Comment