【例64.1】 二维数组转置

解题思路

用长度nm一维数组存原矩阵，原坐标(i,j)下标im+j。转置输出先枚举原列j，再枚举原行i。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

第一行先输出转置后维度m n；不能开20000×20000数组。

复杂度

时间O(nm)，空间O(nm)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n * m);
    for (int &x : a)
        cin >> x;
    cout << m << " " << n << "\n";
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            if (i)
                cout << " ";
            cout << a[i * m + j];
        }
        cout << "\n";
    }
    return 0;
}