48. Rotate Image

柔情只为你懂 2024-04-18 14:09 57阅读 0赞

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]
    ]

题意：  
给一个nxn的方阵，把它以中心元素为中点，顺时针旋转90。不能借助其它的辅助矩阵来完成。

解题思路：  
既然不能借助于辅助矩阵来完成旋转，那么显然就只能探究矩阵旋转前后坐标的对应关系了。

我们先来探究一下，点  P = ( x , y ) P=(x,y) P=(x,y) 以原点为中心，顺时针旋转90度 后得到的  P ′ = ( x ′ , y ′ ) P&\#x27;=(x&\#x27;,y&\#x27;) P′=(x′,y′) 与 P P P 本身有什么关系。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70]  
如上图所示， A A A 是原点， P P P 是待顺时针旋转的点， P ′ P&\#x27; P′ 是旋转得到的目标点。 Q Q Q 是 P P P 关于一、三象限角平分线的对称点。  
根据以上已知条件，我们可以得到：  
 ∠ P A P ′ = 9 0 。 , ∠ F A C = 4 5 。 ∠ F A P = ∠ Q A F \\angle PAP&\#x27;=90^。,\\angle FAC=45^。\\angle FAP=\\angle QAF ∠PAP′=90。,∠FAC=45。∠FAP=∠QAF，  
Ok,因为 ∠ P A P ′ = 90 , ∠ B A C = 90 \\angle PAP&\#x27;=90, \\angle BAC=90 ∠PAP′=90,∠BAC=90 ，因此 ∠ B A P ′ = ∠ C A P \\angle BAP&\#x27;= \\angle CAP ∠BAP′=∠CAP 。  
而 ∠ F A P \\angle FAP ∠FAP 可以看成两个角的和： ∠ F A P = ∠ F A C + ∠ C A P \\angle FAP=\\angle FAC +\\angle CAP ∠FAP=∠FAC\+∠CAP,  
 ∠ Q A F \\angle QAF ∠QAF 可以看成三个角的和： ∠ Q A F = ∠ Q A B + ∠ B A P ′ + ∠ P ′ A F \\angle QAF=\\angle QAB +\\angle BAP&\#x27; +\\angle P&\#x27;AF ∠QAF=∠QAB\+∠BAP′\+∠P′AF 。  
又因为 ∠ F A P = ∠ Q A F \\angle FAP=\\angle QAF ∠FAP=∠QAF,于是有： ∠ F A C + ∠ C A P = ∠ Q A B + ∠ B A P ′ + ∠ P ′ A F \\angle FAC +\\angle CAP=\\angle QAB +\\angle BAP&\#x27; +\\angle P&\#x27;AF ∠FAC\+∠CAP=∠QAB\+∠BAP′\+∠P′AF,  
其中， ∠ B A P ′ = ∠ C A P \\angle BAP&\#x27;= \\angle CAP ∠BAP′=∠CAP ，于是得到： ∠ F A C = ∠ Q A B + ∠ P ′ A F = 4 5 。 \\angle FAC =\\angle QAB +\\angle P&\#x27;AF=45^。 ∠FAC=∠QAB\+∠P′AF=45。,  
而 ∠ B A P ′ + ∠ P ′ A F \\angle BAP&\#x27; +\\angle P&\#x27;AF ∠BAP′\+∠P′AF刚好也等于 4 5 。 45^。 45。,于是有： ∠ Q A B + ∠ P ′ A F = ∠ B A P ′ + ∠ P ′ A F \\angle QAB +\\angle P&\#x27;AF=\\angle BAP&\#x27; +\\angle P&\#x27;AF ∠QAB\+∠P′AF=∠BAP′\+∠P′AF，即 ∠ Q A B = ∠ B A P ′ \\angle QAB =\\angle BAP&\#x27; ∠QAB=∠BAP′ ===> **Q和P’ 居然是X轴对称的！！！**

于是我们看到得到这么一个结论：  
 P ′ P&\#x27; P′ 可以通过 先把 P P P 按第1、3象限 角平分线对称得到点 Q Q Q ,再把点  Q Q Q 按x轴对称 得到。只不过在方阵中，原点是 ( n 2 , n 2 ) (\\frac\{n\}\{2\},\\frac\{n\}\{2\} ) (2n,2n)。

这种对称关系，在代码中是特别容易实现的，于是我们快速写出解法，值得注意的是，我们只需要遍历一半的元素即可，如果把剩下元素再遍历就会又对称回来了。

class Solution { 
    public:
    	void rotate(vector<vector<int>>& matrix) { 
    		//先1,3象限对角线对称
    		int n = matrix.size();
    		for (int i = 0; i < n; i++)
    		{ 
    			for (int j = 0; j < (n - i); j++)
    			{ 
    				swap(matrix[i][j], matrix[n -1 - j][n-1 - i]);
    			}
    		}
    		//按x轴 上下对称
    		for (int i = 0; i < (n / 2); i++)
    		{ 
    			swap(matrix[i], matrix[n - 1 - i]);
    		}
    	}
    };

结果：

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Rotate Image.  
Memory Usage: 9 MB, less than 85.37% of C++ online submissions for Rotate Image.

既然解决了顺时针旋转90度的问题，那么逆时针旋转90也就会做了：逆时针旋转90度等于顺时针旋转270度，===>顺时针旋转90度，转3次就可以了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/22ec210f47104c668583cf612de27844.png