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?

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

## No comments:

## Post a Comment