解题思路

这道题是矩阵转置的基础题。

1. 什么是转置？

把矩阵沿着“主对角线”（左上到右下）对折，行变成列、列变成行，得到的新矩阵就是转置矩阵，记作 Aᵀ。

比如：

1 2 3        1 2 2
2 2 3   ->   2 2 3
2 2 2        3 3 2

原来第 2 行第 3 列的 3，转置后跑到第 3 行第 2 列。

2. 用数组怎么转？

读入原矩阵 a，然后输出的时候，第 i 行第 j 列输出 a[j][i]。也就是把下标反过来，就完成了转置。

3. 注意输出格式

每行的数字之间用单个空格隔开，每行结束换行。

参考代码

#include <iostream>
using namespace std;
int a[105][105];
int main(){
    // P4524 矩阵转置：输出 A^T，即第 i 行第 j 列输出原来 a[j][i]
    int n;
    cin >> n;
    // 读入原矩阵
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin >> a[i][j];
    // 输出转置矩阵
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout << a[j][i]; // 行列互换
            if(j<n) cout << " "; // 数字之间用空格隔开
        }
        cout << endl;            // 每行结束换行
    }
    return 0;
}

复杂度分析

矩阵是 n×n 的，读入要 O(n²)，输出转置也要 O(n²)，所以总时间复杂度是 O(n²)。题目说 3 ≤ n ≤ 100，最多 100×100=10000 个数字，非常快。

存矩阵需要 n×n 的二维数组，空间复杂度是 O(n²)。