旋转矩阵
一、题目
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
不占用额外内存空间能否做到？
例子：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
|
Leetcode：https://leetcode.cn/problems/rotate-matrix-lcci/
Leetcode：https://leetcode.cn/problems/spiral-matrix
二、思路
和转圈打印矩阵的思路一致，我们用两个坐标作为基准，即左上角的坐标和右下角的坐标。用这两个坐标可以确定矩阵的一圈。当更新完这一圈之后，我们再将左上角的横纵坐标都加一，右下角的横纵坐标都减一，获取到更里层的一圈。直到左上角的指标等于右下角的指标。注意题目是 N*N 的矩阵，所以如果左上角坐标等于右下角坐标时，就不用再旋转了。
那么如何旋转矩阵的一圈呢？我们发现对于 N*N 的一圈，我们只需要旋转 N-1 次即可。比如 4*4 的矩阵，我们以最外圈举例子。第一次，我们需要进行
1
2
3
4
| (0, 0) -> (0, 3)
(0, 3) -> (3, 3)
(3, 3) -> (3, 0)
(0, 0) -> (3, 0)
|
所以我们先保存 (0, 0) 位置的元素，然后让(3, 0) 先赋给 (0, 0)，然后依次旋转。接下来是 (0, 1)、(0, 2)。一圈我们变化 3 次。
重点是如何表示坐标，如下的代码较为清晰。
三、代码
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
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <vector>
#include <iostream>
class Solution {
public:
void rotate(std::vector<std::vector<int>>& matrix) {
if (matrix.empty()) {
return;
}
int lu_row = 0, lu_line = 0;
int rd_row = matrix.size()-1, rd_line = matrix[0].size()-1;
for (; lu_row < rd_row && lu_line < rd_line;) {
rotate_edge(matrix, lu_row++, lu_line++, rd_row--, rd_line--);
}
}
private:
void rotate_edge(std::vector<std::vector<int>>& matrix, int lu_row, int lu_line, int rd_row, int rd_line) {
int count = rd_row - lu_row;
int tmp = 0;
for (int i = 0; i < count; ++i) {
tmp = matrix[lu_row][lu_line+i];
matrix[lu_row][lu_line+i] = matrix[rd_row-i][lu_line];
matrix[rd_row-i][lu_line] = matrix[rd_row][rd_line-i];
matrix[rd_row][rd_line-i] = matrix[lu_row+i][rd_line];
matrix[lu_row+i][rd_line] = tmp;
}
}
};
void print_matrix(const std::vector<std::vector<int>>& matrix) {
for (size_t i = 0; i < matrix.size(); ++i) {
for (size_t j = 0; j < matrix[i].size(); ++j) {
std::cout << matrix[i][j] << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
}
int main() {
Solution s;
std::vector<std::vector<int>> matrix{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
s.rotate(matrix);
print_matrix(matrix);
return 0;
}
|
时间复杂度 O(N*N)，空间复杂度 O(1)