leetcode之hot100---48旋转图像（C++）
思路一：四元素旋转
原理：
由下图可知，原图中的第一行旋转后被放置最后一列，同时，对于数字‘1’，原本在第一行中第一个位置，经旋转后变为第一列的第一个位置
因此可以得到原本第 i 行第 j 列的元素经顺时针旋转后会变成倒数第 i 列的第 j 个位置
从数组的角度可以得到matrix[row][col]经过旋转后会到达matrix[n - col - 1][row]
那么数字‘3’经过旋转会到达什么位置？
由下图可知，数字‘3’原本是最后一列的第一个元素，经过旋转后变成了最后一行的第一个元素
因此从数组的角度可以得到matrix[n - col - 1][row]经过旋转后会到达matrix[n - row - 1][n - col - 1]
同理可得， matrix[n - row - 1][n - col - 1]经过旋转后会到达matrix[col][n - row - 1]
matrix[col][n - row - 1]经过旋转后会到达 matrix[row][col]
为了完成旋转操作，我们可以将矩阵分为多层，每一层是一个环状结构：
- 最外层由矩阵的边界元素组成。
- 次外层由次边界元素组成。
- 依次类推，直到矩阵中心。
在每一层中，我们只需要处理每一层的“左上角的四分之一”，因为剩余的部分会在旋转过程中被自动覆盖。
外层循环处理的是矩阵的“层级”。对于一个大小为n x n的矩阵，层数一共有n / 2层（向下取整）。因此，row的范围是从0到n / 2，表示只需要处理一半的行（从上到中间的部分）。举例解释：
- 如果矩阵大小为 4x4，则有 2 层：第 1 层是外圈，涉及行
row = 0，第 2 层是内圈，涉及行row = 1。- 如果矩阵大小为 5x5，则有 2 层：第 1 层是外圈，涉及行
row = 0，第 2 层是内圈，涉及行row = 1。内层循环处理的是当前层中的列。对于每一层，只需要处理当前层前半部分的列，因为旋转的对称特性会自动覆盖后半部分的列。因此，
col的范围是0到(n + 1) / 2，因为每一层只需要处理矩阵左上角的四分之一（即前半部分列）举例解释：
- 例如，如果矩阵大小为 4x4，则每一层中，列的范围是
0到(n + 1) / 2（向上取整），即处理前 2 列。- 如果矩阵大小为 5x5，则每一层中，列的范围仍是
0到(n + 1) / 2，即处理前 3 列。
详细代码如下：
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
int temp;//临时变量
for(int row = 0; row < n / 2; row++){
for(int col = 0; col < (n + 1) / 2; col++){
int temp = matrix[row][col];
matrix[row][col] = matrix[n - col - 1][row];
matrix[n - col - 1][row] = matrix[n - row - 1][n - col - 1];
matrix[n - row - 1][n - col - 1] = matrix[col][n - row - 1];
matrix[col][n - row - 1] = temp;
}
}
}
};- 时间复杂度：O(N²)
- 空间复杂度：O(1)
思路二：翻转
先对矩阵进行水平翻转
然后再对矩阵基于对角线进行翻转 ，就可以得到原矩阵经过顺时针翻转后的矩阵
代码表示如下：
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
//水平翻转，一共有N²/n个数字组队需要交换
//i表示行，只有N/2行组队需要交换，因此i的范围是0~（N-1）/2
//j表示列，每一列的数字都需要进行交换，因此j的范围是0~N
for(int i = 0; i < n / 2; i++){
for(int j = 0; j < n; j++){
swap(matrix[i][j], matrix[n - i - 1][j]);
}
}
//主对角线翻转，只需要交换（N²-N）/2个数字
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
swap(matrix[i][j], matrix[j][i]);
}
}
}
};