# 旋转图像（48）
# 题目
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
# 说明
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
# 示例
给定
matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
]
2
3
4
5
6
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
2
3
4
5
给定
matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
]
2
3
4
5
6
7
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
2
3
4
5
6
# 算法
# 由外向内原地旋转
观察实例可知，图像顺时针旋转90度可以分解为：先旋转最外的一圈数字；然后依次向内旋转第二圈数字...直到旋转最内一圈数字
我们可以设定四个指针指向每一圈的四个边的数字，初始指向[0,0]、[0,n]、[n,n]、[n,0]四个点（n=matrix.length-1），我们每次旋转（交换）这四个数字，然后指针后移（上边的指针右移；右边的指针下移；下边的指针左移；左边的指针上移），直到指向matrix.length-i*2-1（i指当前处于第i层，从0开始；因为每向内一层头尾要减去两个，所以-i*2;因为最后一个位置是顺时针边的指针的初始位置，所以-1）；直到i < ~~(matrix.length/2)循环结束，因为当行数（或列数）为偶数时，我们交换到第matrix.length/2层，当行数为奇数时，我们交换到(matrix.length-1)/2层，最中间一个数字不用交换
每次遍历完一层时，我们要向内一层交换，此时需要重置指针到初始位置（上边的指针重置到最左侧；右边的指针重置到最上边；下边的指针重置到最右侧；左边的指针重置到最下侧），我们需要让控制层的变量向内一层（比如上边的变量[x,y]就需要x++；右边的变量[x,y]就需要y--）；然后让控制每一层位置的变量重置到初始位置（比如上边的变量[x,y]就需要让y=i；右边的变量[x,y]就需要让x=matrix.length-i）
export const rotate = (matrix) => {
if (!matrix.length || matrix.length === 1) return matrix;
const matrixWidth = matrix.length;
let tx = 0,
ty = 0;
let rx = 0,
ry = matrixWidth - 1;
let bx = matrixWidth - 1,
by = matrixWidth - 1;
let lx = matrixWidth - 1,
ly = 0;
for (let i = 0; i < ~~(matrixWidth / 2); ) {
for (let j = 0; j < matrixWidth - i * 2 - 1; j++) {
const temp = matrix[tx][ty];
matrix[tx][ty] = matrix[lx][ly];
matrix[lx][ly] = matrix[bx][by];
matrix[bx][by] = matrix[rx][ry];
matrix[rx][ry] = temp;
ty++;
rx++;
by--;
lx--;
}
tx++;
ry--;
bx--;
ly++;
i++;
ty = i;
rx = i;
by = matrixWidth - 1 - i;
lx = matrixWidth - 1 - i;
}
return matrix;
};
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
35
# 翻转图像
可以将图像先沿水平线翻转；然后沿主对角线（左上到右下的对角线）翻转
export const rotate = (matrix) => {
for (let i = 0; i < ~~(matrix.length / 2); i++) {
[matrix[i], matrix[matrix.length - 1 - i]] = [matrix[matrix.length - 1 - i], matrix[i]];
}
for (let i = 0; i < matrix.length - 1; i++) {
for (let j = i + 1; j < matrix.length; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
return matrix;
};
2
3
4
5
6
7
8
9
10
11
# 原地旋转
观察第二个例子中，我们旋转前的第二行[2,4,8,10]旋转后成为了倒数第二列[2,4,8,10]，所以我们可以推出matrix[row][col] -> matrix[col][matrix.length-1-row]
同理，旋转前的倒数第二列[9，8，6，12]旋转后成为了倒数第二行[12,6,8,9]，所以我们可以推出matrix[col][matrix.length-1-row] -> matrix[matrix.length-1-row][matrix.length-1-col]
旋转前的第二行[13,3,6,7]旋转后成为了第二列[13,3,6,7]，所以我们可以推出matrix[matrix.length-1-row][matrix.length-1-col] -> matrix[matrix.length-1-col][row]
旋转前的第二列[1,4,3,14]旋转后成为了第二行[14,3,4,1]，所以我们可以推出matrix[martix.length-1-col][row] -> matrix[row][col]
因为我们是一行一列的旋转，所以我们使用双循环来实现旋转，外层循环控制行（列），内存循环控制当前行（列）内的每一个元素。外层只遍历一半的图形高度（宽度）即可，所以循环范围[0, Math.floor(matrix.length/2))；内层循环按照图形的高度（宽度），如果图形高度是偶数则遍历范围[0, Math.floor(matrix.length/2))，如果图形高度是奇数则遍历范围[0, Math.floor(matrix.length/2)+1)
export const rotate = (matrix) => {
const n = matrix.length;
for (let i = 0; i < Math.floor(n / 2); i++) {
for (let j = 0; j < Math.floor((n + 1) / 2); j++) {
const temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;
}
}
return matrix;
};
2
3
4
5
6
7
8
9
10
11
12
13