分类:algorithm| 发布时间:2016-10-13 23:14:00
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
将一个 n x n 的 2D 矩阵顺时针 90 度旋转。
在可以使用额外的空间的情况下很简单。
1 2 3 7 4 1
4 5 6 ==> 8 5 2
7 8 9 9 6 3
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
auto save = matrix;
const int n = matrix.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
matrix[j][n - 1 - i] = save[i][j];
}
}
}
};
如果要 in-place 旋转的话就需要一点技巧了。
1 2 3 7 8 9 7 4 1
4 5 6 ==> 4 5 6 ==> 8 5 2
7 8 9 1 2 3 9 6 3
可以先按行倒转,然后按反对角线进行翻转。
/*
* clockwise rotate
* first reverse up to down, then swap the symmetry
* 1 2 3 7 8 9 7 4 1
* 4 5 6 => 4 5 6 => 8 5 2
* 7 8 9 1 2 3 9 6 3
*/
class Solution {
public:
void rotate(vector<vector<int> > &matrix) {
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
};