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?
Solution:
It is not difficult to come out a solution. But it is a little bit tricky when do this in place.
We can treat the matrix as a layered structure. And we can rotate the image layer by layer.
For each layer, we process it pixel by pixel, we only need a temp variable to help the swap up->temp, left->up, bottom->left, right->bottom, temp->right;
Time complexity: O(n*n) space: O(1)
public void rotate(int[][] matrix) {
if(matrix==null || matrix.length<=1 || matrix[0].length<=1) return;
int n=matrix.length;
int layer=0;
while(layer<n/2){
for(int i=layer;i<n-1-layer;i++){
int temp=matrix[layer][i];
matrix[layer][i]=matrix[n-1-i][layer];
matrix[n-1-i][layer]=matrix[n-1-layer][n-i-1];
matrix[n-1-layer][n-1-i]=matrix[i][n-1-layer];
matrix[i][n-1-layer]=temp;
}
layer++;
}
return;
}
No comments:
Post a Comment