C++ 程序 查找矩阵的转置

矩阵的转置是通过将行变为列，列变为行来获得的。换句话说，将 A [i] [j] 改为 A [j] [i] 获得 A [ ] [ ] 的转置。

对于方形阵列：

下面的程序查找 A [ ] [ ] 的转置并将结果存储在 B [ ] [ ] 中，我们可以为不同的维度更改 N。

// C++ 程序查找矩阵的转置
#include <bits/stdc++.h>
using namespace std;
#define N 4
 
// 此函数将 A [ ] [ ] 的转置存储在 B [ ] [ ] 中
void transpose(int A[][N],
               int B[][N])
{
    int i, j;
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            B[i][j] = A[j][i];
}
 
// 主函数
int main()
{
    int A[N][N] = {{1, 1, 1, 1},
                   {2, 2, 2, 2},
                   {3, 3, 3, 3},
                   {4, 4, 4, 4}};
 
    int B[N][N], i, j;
 
    transpose(A, B);
 
    cout << "Result matrix is ";
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
           cout << " " << B[i][j];
        cout <<"";
    }
    return 0;
}  

输出：

结果矩阵是
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 **4**

时间复杂度： O(N*N)，因为有两个嵌套循环。

空间复杂度： O(N*N)，因为创建了2D数组以存储转置。

对于长方形矩阵：

下面的程序查找 A [ ] [ ] 的转置并将结果存储在 B [ ] [ ] 中。

// C++程序查找矩阵的转置
#include <bits/stdc++.h>
using namespace std;
#define M 3
#define N 4
 
// 此函数将 A [ ] [ ] 的转置存储在 B [ ] [ ] 中
void transpose(int A[][N], int B[][M])
{
    int i, j;
    for(i = 0; i < N; i++)
        for(j = 0; j < M; j++)
            B[i][j] = A[j][i];
}
 
// 主函数
int main()
{
    int A[M][N] = {{1, 1, 1, 1},
                   {2, 2, 2, 2},
                   {3, 3, 3, 3}};
 
    // 注意 B [ ] [ ] 的维度
    int B[N][M], i, j;
 
    transpose(A, B);
 
   cout << "Result matrix is ";
    for(i = 0; i < N; i++)
    {
        for(j = 0; j < M; j++)
            cout << " " << B[i][j];

        cout << "";
    }
    return 0;
}  

输出：

结果矩阵是
1 2 3 
1 2 3 
1 2 3 
1 2 3

时间复杂度： O(N*M)，因为有两个嵌套循环。

空间复杂度： O(N*M)，因为创建了2D数组以存储转置。

对于方形矩阵的原地转置：

// C++程序实现
// 上面的方法
#include <bits/stdc++.h>
using namespace std;
 
#define N 4
 
// 将 A [ ][ ] 转换为其转置
void transpose(int A[][N])
{
    for (int i = 0; i < N; i++)
        for (int j = i+1; j < N; j++)
            swap(A[i][j], A[j][i]);
}
 
// 主函数
int main()
{
    int A[N][N] = {{1, 1, 1, 1},
                   {2, 2, 2, 2},
                   {3, 3, 3, 3},
                   {4, 4, 4, 4}};
 
    transpose(A);
 
    printf("Modified matrix is ");
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
           printf("%d ", A[i][j]);
        printf("");
    }
 
    return 0;
}  

输出：

Modified matrix is
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

时间复杂度： O(n)

• 转置的时间复杂度为O(n + m)，其中n是列数，m是矩阵中非零元素的数量。
• 使用单位矩阵作为参考矩阵转置矩阵的计算时间为O(m*n)。
• 假设给定的矩阵是一个方阵，运行时间将为O(n 2 )。

辅助空间： O(1)。