[Day16]48. Rotate Image

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:

1. 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

2. 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.

3. 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

4. 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;
            }
        }
    }