A MEDIUM problem, very interesting.
DESCRIPTION:
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?
ANALYSIS:
-
First, I can do the rotate on paper, from 22, 33, 44 to 55.And I noticed that it can split into layer by layer to rotate. So, we can do this loop just like peeling the onion.
to_define_cycle Then, I started to find the rule and relation of the transformation of the number's two coordinates. At first, I assign 'i=0' and I didn't take 'i' into consideration. After strip the outermost layer, 'i' would change, so I think about 'i'. Then start the formula on the second draft paper. Finally, figure out the plausible formula.
-
Finishing the above steps, I start coding. To achieve 'in-place', I use 'temp'. One thing hasn't be solve is the range of 'i' and 'j' in the loop. Think about peeling the onion, I have to admit my poor imagination so I draw another two of 1010 and 1111. Then it's clear enough.
to_define_i
- After coding done, I submit it immediately without test. The first submission WA because of my misunderstanding of 'clockwise' and 'anti-clockwise'... Simply modify my procedure and submit again, AC!
SOLUTION:
public void rotate(int[][] matrix) {
int n=matrix.length;
for(int i=0;i<(n+1)/2;i++){
for(int j=i;j<n-i-1;j++){
int temp=matrix[i][j];
matrix[i][j]=matrix[n-1-j][i];
matrix[n-1-j][i]=matrix[n-1-i][n-1-j];
matrix[n-1-i][n-1-j]=matrix[j][n-1-i];
matrix[j][n-1-i]=temp;
}
}
}
