转置矩阵 图解题解

这道题到底在问什么

输入

matrix=[[1,2,3],[4,5,6],[7,8,9]]

输出

[[1,4,7],[2,5,8],[3,6,9]]　方阵沿对角线翻折

输入

matrix=[[1,2,3],[4,5,6]]

输出

[[1,4],[2,5],[3,6]]　2 行 3 列变成 3 行 2 列

先想最直接的笨办法

搭一个 4 行 2 列的空架子,圆点表示还没填。注意它的形状,行数等于原来的列数,列数等于原来的行数,正好掉了个个儿。接下来一个一个把数搬进来。（动画第 6 步）

最优解：一步一步想明白

1. 3记牢这把尺子:新坐标 (i,j) 去原矩阵的 (j,i) 取数。后面每一帧都在套它。
2. 4m=2 行,n=4 列,转置后会变成 4 行 2 列这是原矩阵,2 行 4 列,一共 8 个数。目标是把它翻成 4 行 2 列。先记住它现在的样子,等会儿对比着看。
3. 5对角线上的 (0,0)、(1,1) 不动,其余元素以这条线为镜子对调转置的几何直觉:沿着左上到右下这条主对角线翻折。对角线上的数原地不动,其它数像照镜子一样,行列坐标对调位置。
4. 6行列互换:原来 2×4,新矩阵就是 4×2,先开一个空的搭一个 4 行 2 列的空架子,圆点表示还没填。注意它的形状,行数等于原来的列数,列数等于原来的行数,正好掉了个个儿。接下来一个一个把数搬进来。
5. 7第 0 个 · 原坐标 (0,0) → 新坐标 (0,0),行列互换从原矩阵 第 0 行第 0 列 起步,读到的值是 1。它要搬去新矩阵 第 0 行第 0 列,注意两个坐标对调了。
6. 8ans[0][0] = matrix[0][0] = 1把 1 写进新矩阵 第 0 行第 0 列。看坐标:原来是 (0,0),现在是 (0,0),两个下标对调,这就是转置。
7. 9第 1 个 · 原坐标 (1,0) → 新坐标 (0,1),行列互换接着读原矩阵 第 1 行第 0 列 的 5,准备搬到新矩阵 第 0 行第 1 列。
8. 10ans[0][1] = matrix[1][0] = 5把 5 落到新矩阵 第 0 行第 1 列,第 0 行凑齐了。这一行 1、5,正好是原矩阵第 0 列那一竖排。
9. 11第 2 个 · 原坐标 (0,1) → 新坐标 (1,0),行列互换新矩阵这一行填满了,换行。回原矩阵读 第 0 行第 1 列 的 2,它会落到新矩阵 第 1 行第 0 列,开启新一行。
10. 12ans[1][0] = matrix[0][1] = 2把 2 写进新矩阵 第 1 行第 0 列。看坐标:原来是 (0,1),现在是 (1,0),两个下标对调,这就是转置。
11. 13第 3 个 · 原坐标 (1,1) → 新坐标 (1,1),行列互换接着读原矩阵 第 1 行第 1 列 的 6,准备搬到新矩阵 第 1 行第 1 列。
12. 14ans[1][1] = matrix[1][1] = 6把 6 落到新矩阵 第 1 行第 1 列,第 1 行凑齐了。这一行 2、6,正好是原矩阵第 1 列那一竖排。
13. 15第 4 个 · 原坐标 (0,2) → 新坐标 (2,0),行列互换新矩阵这一行填满了,换行。回原矩阵读 第 0 行第 2 列 的 3,它会落到新矩阵 第 2 行第 0 列,开启新一行。
14. 16ans[2][0] = matrix[0][2] = 3把 3 写进新矩阵 第 2 行第 0 列。看坐标:原来是 (0,2),现在是 (2,0),两个下标对调,这就是转置。
15. 17第 5 个 · 原坐标 (1,2) → 新坐标 (2,1),行列互换接着读原矩阵 第 1 行第 2 列 的 7,准备搬到新矩阵 第 2 行第 1 列。
16. 18ans[2][1] = matrix[1][2] = 7把 7 落到新矩阵 第 2 行第 1 列,第 2 行凑齐了。这一行 3、7,正好是原矩阵第 2 列那一竖排。
17. 19第 6 个 · 原坐标 (0,3) → 新坐标 (3,0),行列互换新矩阵这一行填满了,换行。回原矩阵读 第 0 行第 3 列 的 4,它会落到新矩阵 第 3 行第 0 列,开启新一行。
18. 20ans[3][0] = matrix[0][3] = 4把 4 写进新矩阵 第 3 行第 0 列。看坐标:原来是 (0,3),现在是 (3,0),两个下标对调,这就是转置。
19. 21第 7 个 · 原坐标 (1,3) → 新坐标 (3,1),行列互换接着读原矩阵 第 1 行第 3 列 的 8,准备搬到新矩阵 第 3 行第 1 列。
20. 22ans[3][1] = matrix[1][3] = 8把 8 落到新矩阵 第 3 行第 1 列,第 3 行凑齐了。这一行 4、8,正好是原矩阵第 3 列那一竖排。
21. 238 个数全部就位,返回这个新矩阵8 个数全搬完了。新矩阵是 [1,5]、[2,6]、[3,7]、[4,8],4 行 2 列。和原来的 2 行 4 列一对比,长宽互换了,数字一个没少。
22. 24新矩阵第 0 列 1、2、3、4 = 原矩阵第 0 行再回看一眼最直观的对应:新矩阵竖着的第 0 列是 1、2、3、4,正好是原矩阵横着的第 0 行。行变列、列变行,这就是转置的全貌。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        return list(zip(*matrix))

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> ans(n, vector<int>(m));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                ans[i][j] = matrix[j][i];
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int[][] transpose(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] ans = new int[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                ans[i][j] = matrix[j][i];
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问