C++程序 矩阵沿对角线的镜像

给定一个 N x N 的二维数组，打印一个沿对角线镜像的矩阵。我们需要以这样的方式打印结果：将对角线上方的三角形值与下方的交换，如镜像图像交换。以矩阵布局打印获取的二维数组。

例子：

输入: int mat[][] = {{1 2 4 }
                       {5 9 0}
                       {3 1 7}}
输出：  1 5 3 
       2 9 1
       4 0 7

输入: mat[][] = {{1  2  3  4 }
                 {5  6  7  8 }
                 {9  10 11 12}
                 {13 14 15 16}}
输出： 1 5 9 13 
       2 6 10 14  
       3 7 11 15 
       4 8 12 16 

一个 简单的解决方案 涉及额外的空间。我们遍历所有正左对角线 (从右到左)。在对角线遍历过程中，我们先将所有元素推入堆栈，然后再次遍历并用堆栈元素替换对角线的每个元素。

下面的实现是上述思路的实现。

// 简单的 CPP 程序，用于查找沿对角线的矩阵镜像。
#include 
using namespace std;

const int MAX = 100;

void imageSwap(int mat[][MAX], int n)
{
    // 起始于矩阵的第一行的对角线
    int row = 0;

    // 遍历所有的右上对角线
    for (int j = 0; j < n; j++) {

        // 这里我们使用堆栈来翻转对角线上元素的顺序
        stack s;
        int i = row, k = j;
        while (i < n && k >= 0)
            s.push(mat[i++][k--]);

        // 将所有元素按相反顺序推回矩阵中
        i = row, k = j;
        while (i < n && k >= 0) {
            mat[i++][k--] = s.top();
            s.pop();
        }
    }

    // 对于起始于最后一列的对角线，进行相同的处理
    int column = n - 1;
    for (int j = 1; j < n; j++) {

        // 这里我们使用堆栈来翻转对角线上元素的顺序
        stack s;
        int i = j, k = column;
        while (i < n && k >= 0)
            s.push(mat[i++][k--]);

        // 将所有元素按相反顺序推回矩阵中
        i = j;
        k = column;
        while (i < n && k >= 0) {
            mat[i++][k--] = s.top();
            s.pop();
        }
    }
}

// 实用函数：打印一个矩阵
void printMatrix(int mat[][MAX], int n)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << mat[i][j] << " ";
        cout << endl;
    }
}

// 主函数：测试上面的函数
int main()
{
    int mat[][MAX] = { { 1, 2, 3, 4 },
                       { 5, 6, 7, 8 },
                       { 9, 10, 11, 12},
                       { 13, 14, 15, 16 } };
    int n = 4;
    imageSwap(mat, n);
    printMatrix(mat, n);
    return 0;
}  

输出：

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

时间复杂度： O(n*n)

辅助空间： O(1)

一个 高效的解决方案 是，如果我们观察一个输出矩阵，我们注意到我们只需要交换 (mat[i][j] 到 mat[j][i])。
下面是上述思路的实现。

// 高效的CPP程序，用于在对角线上找到矩阵的镜像。
#include
using namespace std;
 
const int MAX = 100;
 
void imageSwap(int mat[][MAX], int n)
{
    // 遍历矩阵并交换mat [i] [j]与mat [j] [i]
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            mat[i][j] = mat[i][j] + mat[j][i] -
                       (mat[j][i] = mat[i][j]);      
}
 
// 实用程序函数来打印矩阵
void printMatrix(int mat[][MAX], int n)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << mat[i][j] << " ";
        cout << endl;
    }
}
 
// 驱动程序测试上述功能
int main()
{
    int mat[][MAX] = { { 1, 2, 3, 4 },
                     { 5, 6, 7, 8 },
                     { 9, 10, 11, 12 },
                     { 13, 14, 15, 16 } };
    int n = 4;
    imageSwap(mat, n);
    printMatrix(mat, n);
    return 0;
}  

输出：

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

时间复杂度： O(n*n)

辅助空间： : O(1)，因为它使用常量空间。