48. Rotate Image
Question
You are given an n x n
2D matrix
representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Algorithm
If you tried do it at one motion, you may not find the answer.
For matrix related questions, there are some useful movement, like image, flip(diagonal and anti-diagonal), if you are solving this kind of problem, try to do such things and find a pattern.
For this question, if you need to rotate a matrix, image first, and then flip once, then you will get the answer.
Code
class Solution {
public void rotate(int[][] matrix) {
image(matrix);
flip(matrix);
}
private void image(int[][] matrix) {
int m = matrix.length;
for (int i = 0; i < m; i++) {
for (int j = i; j < m; j++) {
if (i != j) {
swap(matrix, i, j);
}
}
}
}
private void flip(int[][] matrix) {
int m = matrix.length - 1;
for (int[] row : matrix) {
int i = 0, j = m;
while (i < j) {
int temp = row[i];
row[i] = row[j];
row[j] = temp;
i++;
j--;
}
}
}
private void swap(int[][] matrix, int i, int j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}