Saturday, July 18, 2015

Matrix rotation

There are two kinds of matrix rotation problems: one is to rotate the whole matrix clock-wise by 90 degree,

Input:
1 2 3
4 5 6
7 8 9

Output:
7 4 1
8 5 2
9 6 3

Think about the above a graph process software to rotate the pixels in an image. See this link:
http://www.programcreek.com/2013/01/leetcode-rotate-image-java/

Another way is to shift the elements clock-wise:


Input:
1 2 3
4 5 6
7 8 9

Output:
4 1 2
7 5 3
8 9 6

Here I present solutions to both:
/*
* essentially we treat elements in the matrix as circles, there are total Math.ceil(matrix.length/2) circles.
* However if matrix length is odd, the most inner circle contains one element, we don't need to rotate it.
* so we can deal with Math.floor(matrix.length/2) circles.
*/

public static void rotateMatrix(int[][] matrix){
int num = matrix.length;
for(int i=0; i<num/2; i++){
for(int j=i; j<num-i-1; j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[num-j-1][i];
matrix[num-j-1][i] = matrix[num-i-1][num-j-1];
matrix[num-i-1][num-j-1] = matrix[j][num-i-1];
matrix[j][num-i-1] = temp;
}
}
for(int i=0; i<num; i++)
System.out.println(Arrays.toString(matrix[i]));
}

/*
 * shifting is similar above, we shift Math.floor(matrix.length/2) circle one by one
 */


public static void rotateMatrixByShiftElements(int[][] matrix){
int num = matrix.length;
for(int i=0; i<num/2; i++){
int start = matrix[i][i];
//shift up on column i
for(int row=i; row<num-i-1; row++){
matrix[row][i] = matrix[row+1][i];
}
//shift left on row num-i-1
for(int col=i; col<num-i-1; col++){
matrix[num-i-1][col] = matrix[num-i-1][col+1];
}
//shift down on column num-i-1
for(int row=num-i-1; row>i; row--){
matrix[row][num-i-1] = matrix[row-1][num-i-1];
}
//shift right on row i
for(int col=num-i-1; col>i; col--){
matrix[i][col] = matrix[i][col-1];
}
//the last one!
matrix[i][i+1] = start;
}
for(int i=0; i<num; i++)
System.out.println(Arrays.toString(matrix[i]));
}






No comments:

Post a Comment