leetcode Question 88: Rotate Image

Rotate Image

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
The classic problem in Career Cup book 1.6.
The key idea is to rotate the matrix according to layers. For the nth layer(the out layer), rotate 90 degree is to move all the elements n times in a circle. In each layer, the rotation can be performed by first swap 4 corners, then swap 4 elements next to corner until the end of each line.


Code:

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = matrix.size();
        for (int layer=0; layer<n/2; layer++){
            int first = layer;
            int last  = n-1-layer; 
            for (int i=first;i<last;i++){
                int offset = i-first;
                int top = matrix[first][i];
                //left->top            
                matrix[first][i]=matrix[last-offset][first];
                //bottom->top
                matrix[last-offset][first] = matrix[last][last-offset];
                //right->bottom
                matrix[last][last-offset] = matrix[i][last];
                //top->right
                matrix[i][last] = top;
            }
        }
        
    }
};