867. 转置矩阵

给定一个矩阵 A， 返回 A 的转置矩阵。
矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

示例 1：

输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：[[1,4,7],[2,5,8],[3,6,9]]

示例 2：

输入：[[1,2,3],[4,5,6]]
输出：[[1,4],[2,5],[3,6]]

提示：

1 <= A.length <= 1000
1 <= A[0].length <= 1000

思路

两个for循环嵌套
普通的矩阵遍历是

for(i in 行号){
    for(j in 列号){
        print A[i][j]
    }
}

我们需要得到转置结果，所以需要交换遍历顺序
即外层固定列号不变，通过行号改变得到不同行同一列的值

for(j in 列号){
    for(i in 行号){
        print A[i][j]
    }
}

性能分析

时间复杂度O(N^2)，空间复杂度O(N)（新加行的时候需要额外一行用于存储）

具体代码

vector<vector<int>> transpose(vector<vector<int>>& A) {
    int rlen = A.size();  //行大小
    int clen = A[0].size(); //列大小
    vector<vector<int> > res; //结果集
    for(int i = 0; i < clen; i++){ //上方伪代码的实现
        vector<int> tmp;
        for(int j = 0; j < rlen; j++){
            tmp.push_back(A[j][i]);
        }
        res.push_back(tmp);
    }
    return res;
}