用100道题拿下你的算法面试（矩阵篇-2）：求转置矩阵

一、面试问题给定一个二维矩阵 mat [][]计算其转置矩阵。矩阵的转置是通过将原矩阵的所有行转换为列、所有列转换为行得到的。示例 1输入以下矩阵mat[][] [ [1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [4, 4, 4, 4] ]得到以下输出[ [1, 2, 3 ,4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4] ]解释如下输出为输入矩阵的转置其中每一行变为一列。该重排方式使得原矩阵中的竖直模式在结果中变为水平模式。示例 2输入以下矩阵mat[][] [ [1, 2], [9, -2] ]得到以下输出[ [1, 9], [2, -2] ]解释如下输出为输入矩阵的转置其中每一行变为一列。该重排方式使得原矩阵中的竖直模式在结果中变为水平模式。二、【解法一】暴力法求解矩阵转置 —— 时间复杂度 O (m*n)空间复杂度 O (m*n)(一) 解法思路该思路是创建一个新矩阵通过交换索引将原矩阵的行转换为列 —— 原矩阵中位置 [i][j] 上的元素在转置矩阵中变为 [j][i]。逐步骤实现初始化一个大小为 m × n 的新矩阵行列互换。遍历原矩阵的每一个元素。将原矩阵中第 r 行第 c 列的每个元素赋值给新矩阵中第 c 行第 r 列的位置。返回新的转置矩阵。(二) 使用 5 种语言实现1. C#include iostream #include vector using namespace std; vectorvectorint transpose(vectorvectorint mat) { int rows mat.size(); int cols mat[0].size(); // 创建一个 cols 行 rows 列的结果矩阵用于存储转置矩阵 vectorvectorint tMat(cols, vectorint(rows)); // 通过将行与列互换填充转置矩阵 for (int i 0; i rows; i) { for (int j 0; j cols; j) { // 赋值转置后的值 tMat[j][i] mat[i][j]; } } return tMat; } int main() { vectorvectorint mat { {1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4} }; vectorvectorint res transpose(mat); for (auto row : res) { for (auto elem : row) { cout elem ; } cout \n; } return 0; }2. Javaimport java.util.ArrayList; import java.util.Scanner; public class DSA { public static ArrayListArrayListInteger transpose(int[][] mat) { int rows mat.length; int cols mat[0].length; // 创建一个 cols 行 rows 列的结果矩阵用于存储转置矩阵 ArrayListArrayListInteger tMat new ArrayList(); // 通过将行与列互换填充转置矩阵 for (int i 0; i cols; i) { ArrayListInteger row new ArrayList(); for (int j 0; j rows; j) { // 赋值转置后的值 row.add(mat[j][i]); } tMat.add(row); } return tMat; } public static void main(String[] args) { int[][] mat { {1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4} }; ArrayListArrayListInteger res transpose(mat); for (ArrayListInteger row : res) { for (int elem : row) { System.out.print(elem ); } System.out.println(); } } }3. Pythondef transpose(mat): rows len(mat) cols len(mat[0]) # 创建一个 cols 行 rows 列的结果矩阵用于存储转置矩阵 tMat [[0 for _ in range(rows)] for _ in range(cols)] # 通过将行与列互换填充转置矩阵 for i in range(rows): for j in range(cols): # 赋值转置后的值 tMat[j][i] mat[i][j] return tMat if __name__ __main__: mat [[1, 1, 1, 1],[2, 2, 2, 2],[3, 3, 3, 3], [4, 4, 4, 4]] res transpose(mat) for row in res: for elem in row: print(elem, end ) print()4. C#using System; using System.Collections.Generic; public class DSA { public static ListListint transpose(int[,] mat) { int rows mat.GetLength(0); int cols mat.GetLength(1); // 创建一个 cols 行 rows 列的结果矩阵用于存储转置矩阵 ListListint tMat new ListListint(); // 通过将行与列互换填充转置矩阵 for (int j 0; j cols; j) { Listint row new Listint(); for (int i 0; i rows; i) { // 赋值转置后的值 row.Add(mat[i, j]); } tMat.Add(row); } return tMat; } public static void Main() { int[,] mat { {1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4} }; ListListint res transpose(mat); int rows res.Count; int cols res[0].Count; for (int i 0; i rows; i) { for (int j 0; j cols; j) { Console.Write(res[i][j] ); } Console.WriteLine(); } } }5. JavaScriptfunction transpose(mat) { const rows mat.length; const cols mat[0].length; // 创建一个 cols 行 rows 列的结果矩阵用于存储转置矩阵 const tMat new Array(cols).fill(0).map(() new Array(rows).fill(0)); // 通过将行与列互换填充转置矩阵 for (let i 0; i rows; i) { for (let j 0; j cols; j) { // 赋值转置后的值 tMat[j][i] mat[i][j]; } } return tMat; } // 测试代码 const mat [[1, 1, 1, 1],[2, 2, 2, 2],[3, 3, 3, 3], [4, 4, 4, 4]]; const res transpose(mat); for (const row of res) { console.log(row.join( )); }(三)代码输出和算法复杂度输出1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4时间复杂度O(m*n)空间复杂度O(m*n)三、【解法二】适用于方阵的常量空间解法 —— 时间复杂度 O (m*n)空间复杂度 O (1)(一)解法思路这种方法仅适用于方阵行数与列数相等的矩阵。它被称为原地算法因为无需使用任何额外空间即可完成矩阵转置。实现步骤① 初始化两层嵌套循环外层循环i从 0 到 n-1内层循环j从 i1 到 n-1这样可以避开对角线元素和已经交换过的位置。② 交换元素对每一对位置(i, j)交换mat[i][j]和mat[j][i]这会让元素沿着主对角线对称互换③ 持续交换直到所有上三角区域的元素都与对应的下三角元素完成互换。(二) 使用 5 种语言实现1. C#include iostream #include vector using namespace std; vectorvectorint transpose(vectorvectorint mat) { int n mat.size(); // 遍历矩阵的上三角部分 for (int i 0; i n; i) { for (int j i 1; j n; j) { // 沿对角线交换元素 swap(mat[i][j], mat[j][i]); } } return mat; } int main() { vectorvectorint mat { {1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3 ,3}, {4, 4, 4, 4} }; vectorvectorint res transpose(mat); for (const auto row : res) { for (int elem : row) { cout elem ; } cout endl; } return 0; }2. Javaimport java.util.Arrays; class DSA { public static int[][] transpose(int[][] mat) { int n mat.length; // 遍历矩阵的上三角部分 for (int i 0; i n; i) { for (int j i 1; j n; j) { // 沿对角线交换元素 int temp mat[i][j]; mat[i][j] mat[j][i]; mat[j][i] temp; } } return mat; } public static void main(String[] args) { int[][] mat { {1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4} }; int[][] res transpose(mat); for (int[] row : res) { for (int elem : row) { System.out.print(elem ); } System.out.println(); } } }3. Pythondef transpose(mat): # 行数因为是方阵行和列数相等 n len(mat) # 遍历矩阵的上三角部分 for i in range(n): for j in range(i 1, n): # 沿对角线交换元素 mat[i][j], mat[j][i] mat[j][i], mat[i][j] return mat if __name__ __main__: mat [[1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [4, 4, 4, 4]] res transpose(mat) for row in res: print( .join(map(str, row)))4. C#using System; using System.Collections.Generic; public class DSA { public static ListListint transpose(int[,] mat) { // 行数和列数 int rows mat.GetLength(0); int cols mat.GetLength(1); ListListint result new ListListint(); // 构建转置矩阵 for (int j 0; j cols; j) { Listint row new Listint(); for (int i 0; i rows; i) { row.Add(mat[i, j]); } result.Add(row); } return result; } public static void Main() { int[,] mat { {1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3 ,3}, {4, 4, 4, 4} }; ListListint res transpose(mat); int rows res.Count; int cols res[0].Count; for (int i 0; i rows; i) { for (int j 0; j cols; j) { Console.Write(res[i][j] ); } Console.WriteLine(); } } }5. JavaScriptfunction transpose(mat) { // 行数因为是方阵行和列数相等 const n mat.length; // 遍历矩阵的上三角部分 for (let i 0; i n; i) { for (let j i 1; j n; j) { // 沿对角线交换元素 let temp mat[i][j]; mat[i][j] mat[j][i]; mat[j][i] temp; } } return mat; } // 测试代码 const mat [[1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [4, 4, 4, 4]]; const res transpose(mat); for (const row of res) { console.log(row.join( )); }(三)代码输出和算法复杂度输出1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4时间复杂度O(m*n)空间复杂度O(1)