Matrix Rotation in Java
Rotating Matrix to 90 Clockwise
[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 9 ]
With Matrix Transpose
[ 1 4 7 ]
[ 2 5 8 ]
[ 3 6 9 ]
1) We transpose the matrix 2) And we interchange the columns
public void rotateMatrixRight90Transpose(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
for (int i = 0; i < m; i++) {
for (int j = i; j < n; j++) {
int x = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = x;
System.out.println("IC" + i + ":" + j);
}
}
// swap cols
for (int i = 0; i < m; i++) {
for (int j = 0; j < n / 2; j++) {
// swap mat[i][j] with mat[N-i-1][j]
int temp = mat[i][j];
mat[i][j] = mat[i][n - j - 1];
mat[i][n - j - 1] = temp;
}
}
}
Matrix Rotation with Transpose
<= Original Matrix =>
[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 9 ]
<= After Transpose =>
[ 1 4 7 ]
[ 2 5 8 ]
[ 3 6 9 ]
<= After Rotation =>
[ 7 4 1 ]
[ 8 5 2 ]
[ 9 6 3 ]
Matrix Rotation in Single pass
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < (n + 1) / 2; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1];
matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = matrix[i][j];
matrix[i][j] = temp;
}
}
}
Matrix Rotation with single pass
<= Original Matrix =>
[ 1 2 3 ]
[ 4 5 6 ]
[ 7 8 9 ]
<= After Rotation =>
[ 7 4 1 ]
[ 8 5 2 ]
[ 9 6 3 ]
No comments :
Post a Comment
Please leave your message queries or suggetions.
Note: Only a member of this blog may post a comment.