48. Rotate Image 旋转图像

Medium

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

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:
 
 Given input matrix =
 [
 [1,2,3],
 [4,5,6],
 [7,8,9]
 ],
 
 rotate the input matrix in-place such that it becomes:
 [
 [7,4,1],
 [8,5,2],
 [9,6,3]
 ]
 Example 2:
 
 Given input matrix =
 [
 [ 5, 1, 9,11],  i=0,j=1,n=4
 [ 2, 4, 8,10],
 [13, 3, 6, 7],
 [15,14,12,16]
 ],
 
 rotate the input matrix in-place such that it becomes:
 [
 [15,13, 2, 5],
 [14, 3, 4, 1],
 [12, 6, 8, 9],
 [16, 7,10,11]
 ]
 

这道题让我们将一个n*n的二维矩阵顺时针旋转90度.

解法1

直接计算元素的旋转后的位置. 如图

第一次变换,先计算1的旋转后的位置,1替换3,再计算3的位置,再计算9的位置,再计算7的位置,7的位置正好就是1的位置.所以这种方法每次交换四个位置

/*
     i=0,j=1,n=4时,
     [                          [
     [ 5, 1, 9,11],             [15,13, 2, 5],
     [ 2, 4, 8,10],   ---->     [14, 3, 4, 1],
     [13, 3, 6, 7],             [12, 6, 8, 9],
     [15,14,12,16]              [16, 7,10,11]
     ],                         ]
*/
void rotate2(vector<vector<int>> &matrix){
    int n = matrix.size();
    for (int i = 0; i<n/2; i++) {
        for (int j = i; j<n-1-i; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[n-1-j][i];
            matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
            matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
            matrix[j][n-1-i] = tmp;
        }
    }
}

解法2

先对原来的进行转置矩阵,然后把每一个行的数字翻转就可得到结果

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
        reverse(matrix[i].begin(), matrix[i].end());
    }
}
 
comments powered by Disqus