Find fun in algorithm - Matrix Rotation
by Leon Guo
Matrix Rotation
Question
Given a NxN matrix, where each element in the matrix is integer, write a method to rotate the matrix by 90 degrees.
Answer
We can separate the question to a set of small questions. The matrix could be considered as N/2 layers, which is a circle from innermost to outermost. So the key is swapping the element in each circle.
For example, we have a matrix:
1 | 2 | 3 | 4 | 5 |
6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 |
At first time of computing, in layer one, it’s 1,2,3,4,5
, 5,10,15,20,25
, 25,24,23,22,21
and 21,16,11,6,1
(It’s edges at the outermost). We start from the first element, so move 1 to 5, 5 to 25, 25 to 21 and 21 to 1. Yes it’s a cyclic swap, four times in all. Why four times? Because it’s a matrix and it has four corners. After this action:
21 | 2 | 3 | 4 | 1 |
6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 |
25 | 22 | 23 | 24 | 5 |
Then we move 2 to 4, 4 to 19, 19 to 17 and 17 to 2.
…
After N - 1 times, the matrix is:
21 | 16 | 11 | 6 | 1 |
22 | 7 | 8 | 9 | 2 |
23 | 12 | 13 | 14 | 3 |
24 | 17 | 18 | 19 | 4 |
25 | 22 | 15 | 10 | 5 |
We can find out the outermost layer of the matrix has been completely rotated. Then we need to handle the second layer, which is(except 13
, we needn’t take care about it as 13
at the centre point, so there is no third layer):
7 | 8 | 9 |
12 | 13 | 14 |
17 | 18 | 19 |
…
After process all the N/2 layers, the matrix will be completely rotate:
21 | 16 | 11 | 6 | 1 |
22 | 17 | 12 | 7 | 2 |
23 | 18 | 13 | 8 | 3 |
24 | 19 | 14 | 9 | 4 |
25 | 20 | 15 | 10 | 5 |
Whole java file
package example;
public class Matrix {
/**
* Rotate a matrix, space complexity is O(1), time complexity is O(2N)
* @param matrix the matrix to be rotated
*/
public static void rotate(int[][] matrix) {
for (int i = 0; i < matrix.length / 2; i++) {
int[] layer = matrix[i];
for (int j = i; j < matrix[i].length - i - 1; j++) {
exchange(matrix, layer[j], i, j, 0);
}
}
}
/**
* Exchange the element in matrix
* @param matrix
* @param val The value want to replace to other element
* @param layer The layer of the value
* @param index The index of the value
* @param times The times of the recursion function has been invoked. Because of it's a matrix, so after invoked for 3 times, it will return to the beginning position
*/
private static void exchange(int[][] matrix, int val, int layer, int index, int times) {
if (times > 4) {
return;
}
int tmp = matrix[index][matrix[index].length - layer - 1];
exchange(matrix, tmp, index, matrix[index].length - layer - 1, ++times);
matrix[index][matrix[index].length - layer - 1] = val;
Matrix.printMatrix(matrix);
}
public static void printMatrix(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
System.out.print(matrix[i][j] + ",");
}
System.out.print("\n");
}
System.out.print("\n");
}
public static void main(String[] args) {
int[][] matrix = { {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25} };
Matrix.printMatrix(matrix);
Matrix.rotate(matrix);
Matrix.printMatrix(matrix);
}
}
Subscribe via RSS