48. Rotate Image

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.

Solution 1

此方法是in-place算法。

visited[][]数组记录访问情况,遍历所有位置,如果已访问则跳过。
循环替换矩阵上的每一个位置,如果已经访问过则break。
如果未访问则将要替换位置的值保存,并且在visited[][]数组上记录。
然后继续遍历替换过的位置。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public void rotate(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] visited = new int[m][n];

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(visited[i][j] == 1) continue;
int x = i, y = j;
int value = matrix[i][j];
while(true){
int s = n-1-x, t = y;
if(visited[t][s] == 1) break;
int temp = matrix[t][s];
matrix[t][s] = value;
value = temp;
visited[t][s] = 1;
x = t;
y = s;
}
}
}
}
}

Solution 2

此方法类似Solution 1,但是并非原地算法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public void rotate(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] mat = new int[m][n];

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int s = n-1-i, t = j;
mat[t][s] = matrix[i][j];
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
matrix[i][j] = mat[i][j];
}
}
}
}

Solution 3

辅助方法getPixel计算旋转后的像素位置。
旋转时候矩阵内的四个分区的像素会互相替换。
因此需要将需要旋转的初始位置记录进入队列。
旋转图像时根据getPixel方法计算出需要替换的位置。
然后依次替换像素。

Code

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
26
27
28
29
30
31
32
33
34
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
Queue<Integer> queue = new LinkedList();
for (int p = 0; p < n/2; p++){
for(int q = 0; q < (n+1)/2; q++){
queue.offer(p * n + q);
}
}

while(!queue.isEmpty()){
int i = queue.poll();
int INDEX = i;
boolean flag = true;
int temp = matrix[i/n][i%n];
while(i != INDEX || flag ){
flag = false;
int j = getPixel(n, i);
int swap = matrix[j / n][j % n];
matrix[j / n][j % n] = temp;
temp = swap;
i = j;
}
}
}

private int getPixel(int n, int o){
int row = o / n;
int col = o % n;
int newRow = col;
int newCol = n - (row + 1);
return (newRow * n) + newCol;
}
}
Author

Xander

Posted on

2022-04-18

Updated on

2022-08-30

Licensed under

Comments