C++程序 在原地旋转正方形矩阵的90度 – 1

给定一个正方形矩阵，不使用任何额外的空间将其沿逆时针方向旋转90度。

例子 :

输入:
矩阵:
1 2 3
4 5 6
7 8 9
输出:
3 6 9
2 5 8
1 4 7
给定的矩阵被旋转了90度
逆时针方向。

输入:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
输出:
4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13
给定的矩阵被旋转了90度
逆时针方向。

已讨论了需要使用额外空间的方法 在此处 。

方法: 为了在没有任何额外空间的情况下解决该问题，请将矩阵旋转为正方形的形式，将矩阵分成正方形或循环。 例如，

一个4 X 4矩阵将具有2个循环。第一个循环由它的第1行，最后一列，最后一行和第1列组成。第二个循环由第二行，倒数第二列，倒数第二行和第二列组成。对于每个正方形循环，通过将从顶部到左侧，左侧到底部，底部到右侧并从右侧到顶部依次使用仅使用临时变量交换涉及的元素以逆时针方向旋转相应的单元格来实现此目的。

演示:

第一循环（涉及红色元素）
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

将第一次循环的前四个元素（第一行，最后一行，第一列和最后一列的第一个元素）逆时针旋转。
4 2 3 16
5 6 7 8
9 10 11 12
1 14 15 13

将第一个循环的下一组四个元素逆时针旋转
4 8 3 16
5 6 7 15
2 10 11 12
1 14 9 13

将第一个循环的最后一组四个元素逆时针旋转
4 8 12 16
3 6 7 15
2 10 11 14
1 5 9 13

第二循环（涉及蓝色元素）
4 8 12 16
3 6 7 15
2 10 11 14
1 5 9 13

固定第二个循环
4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13

算法:

1. 在N边长的矩阵中，有N/2个正方形或循环。一次处理一个正方形。运行循环以按周期遍历矩阵，即从0到N/2-1循环，循环计数器是 i
2. 在当前正方形中考虑由4个元素组成的组，在一次旋转4个元素。所以在一个循环中的这样的组数是N-2*i。
3. 因此，在每个循环中从x到N-x-1运行循环，循环计数器是 y
4. 当前组中的元素是(x, y)，(y, N-1-x)，(N-1-x, N-1-y),(N-1-y, x)，现在将这4个元素逆时针旋转，即将元素(x, y) <- (y, N-1-x)，(y, N-1-x)<- (N-1-x, N-1-y)，(N-1-x, N-1-y)<- (N-1-y, x)，(N-1-y, x)<- (x, y)
5. 输出矩阵。

// C++程序，旋转矩阵90度
// 包括头文件
#include <bits/stdc++.h>
#define N 4
using namespace std;
  
void displayMatrix(
    int mat[N][N]);
  
// 一个原位函数，用于
// 将N x N矩阵旋转90度
// 逆时针方向
void rotateMatrix(int mat[][N])
{
    // 一个一个地考虑所有正方形
    for (int x = 0; x < N / 2; x++) {
        // 考虑当前正方形中的4个元素
        for (int y = x; y < N - x - 1; y++) {
            //将当前的单元格存储在 temp 变量中
            int temp = mat[x][y];
  
            //从右向上移动值
            mat[x][y] = mat[y][N - 1 - x];
  
            //从底部向右移动值
            mat[y][N - 1 - x]
                = mat[N - 1 - x][N - 1 - y];
  
            //从左向下移动值
            mat[N - 1 - x][N - 1 - y]
                = mat[N - 1 - y][x];
  
            //将 temp 赋值给左边
            mat[N - 1 - y][x] = temp;
        }
    }
}
  
// 打印矩阵的函数
void displayMatrix(int mat[N][N])
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf("%2d ", mat[i][j]);
  
        printf("
");
    }
    printf("
");
}
  
/*主程序*/
int main()
{
    //测试用例1
    int mat[N][N] = {
        { 1, 2, 3, 4 },
        { 5, 6, 7, 8 },
        { 9, 10, 11, 12 },
        { 13, 14, 15, 16 }
    };
  
    //测试用例2
    /* int mat[N][N] = {
                        {1, 2, 3},
                        {4, 5, 6},
                        {7, 8, 9}
                    };
     */
  
    //测试用例3
    /*int mat[N][N] = {
                    {1, 2},
                    {4, 5}
                };*/
  
    // displayMatrix(mat);
  
    rotateMatrix(mat);
  
    // 输出旋转后新矩阵
    displayMatrix(mat);
  
    return 0;
}  

输出:

 4  8 12 16 
 3  7 11 15 
 2  6 10 14 
 1  5  9 13 

时间复杂度:

• 时间复杂度: O(n*n)，其中 n 是数组的边长。 只需要一次遍历矩阵。
• 空间复杂度: O(1)。 只需要一个固定的空间。