算法题转置矩阵-洪萨配资

转置矩阵

问题描述

给定一个二维整数数组matrix，返回转置矩阵。

转置矩阵是指将原矩阵的行变成列，列变成行后的新矩阵。

如果原矩阵是m x n，那么转置矩阵就是n x m
转置矩阵中位置(i, j)的元素等于原矩阵中位置(j, i)的元素

示例：

输入: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]]

算法思路

直接转置：

创建一个新的结果矩阵，行数为原矩阵的列数，列数为原矩阵的行数
遍历原矩阵的每个元素
将原矩阵中位置(i, j)的元素放到结果矩阵的(j, i)位置
返回转置后的矩阵

核心思想：

转置的本质就是行列互换
对于任意矩阵（包括非方阵），都可以进行转置操作
时间复杂度为 O(m × n)，空间复杂度为 O(m × n)

代码实现

方法一：创建新矩阵

classSolution{/** * 转置矩阵 - 创建新矩阵 * * @param matrix 输入的二维矩阵，维度为 m x n * @return 转置后的矩阵，维度为 n x m * * 算法思路： * 1. 获取原矩阵的行数 m 和列数 n * 2. 创建结果矩阵 transposed，维度为 n x m * 3. 遍历原矩阵每个位置 (i, j) * 4. 将 matrix[i][j] 赋值给 transposed[j][i] */publicint[][]transpose(int[][]matrix){// 获取原矩阵的行数和列数intm=matrix.length;// 原矩阵行数intn=matrix[0].length;// 原矩阵列数// 创建转置矩阵，行数为原矩阵列数，列数为原矩阵行数int[][]transposed=newint[n][m];// 遍历原矩阵的每个元素for(inti=0;i<m;i++){for(intj=0;j<n;j++){// 将原矩阵 (i, j) 位置的元素放到转置矩阵 (j, i) 位置transposed[j][i]=matrix[i][j];}}returntransposed;}}

方法二：原地转置（方阵）

classSolution{/** * 原地转置矩阵 - 仅用于方阵 (m == n) * * @param matrix 输入的方阵 * @return 转置后的方阵（原地修改） * * 仅用于方阵，对于非方阵无法原地转置， * 转置后矩阵维度会发生变化 */publicint[][]transposeInPlace(int[][]matrix){intn=matrix.length;// 只遍历上三角部分，避免重复交换for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){// 交换 matrix[i][j] 和 matrix[j][i]inttemp=matrix[i][j];matrix[i][j]=matrix[j][i];matrix[j][i]=temp;}}returnmatrix;}/** * 根据是否为方阵选择不同策略 */publicint[][]transpose(int[][]matrix){intm=matrix.length;intn=matrix[0].length;// 如果是方阵，原地转置if(m==n){returntransposeInPlace(matrix);}else{// 非方阵必须创建新矩阵int[][]transposed=newint[n][m];for(inti=0;i<m;i++){for(intj=0;j<n;j++){transposed[j][i]=matrix[i][j];}}returntransposed;}}}

算法分析

时间复杂度：O(m × n)
- 需要访问原矩阵的每个元素一次
- 无论是否为方阵，都需要处理所有 m × n 个元素
空间复杂度：
- 创建新矩阵：O(m × n)
  - 需要创建一个新的 n × m 矩阵存储结果
- 原地转置（方阵）：O(1)
  - 只使用常数额外空间，直接在原矩阵上操作

算法过程

1：方阵转置

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

m = 3, n = 3
创建 transposed[3][3]
遍历过程：
- (0,0): transposed[0][0] = matrix[0][0] = 1
- (0,1): transposed[1][0] = matrix[0][1] = 2
- (0,2): transposed[2][0] = matrix[0][2] = 3
- (1,0): transposed[0][1] = matrix[1][0] = 4
- (1,1): transposed[1][1] = matrix[1][1] = 5
- (1,2): transposed[2][1] = matrix[1][2] = 6
- (2,0): transposed[0][2] = matrix[2][0] = 7
- (2,1): transposed[1][2] = matrix[2][1] = 8
- (2,2): transposed[2][2] = matrix[2][2] = 9

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

2：非方阵转置

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

m = 2, n = 3
创建 transposed[3][2]
遍历过程：
- 第0行：transposed[0][0]=1, transposed[1][0]=2, transposed[2][0]=3
- 第1行：transposed[0][1]=4, transposed[1][1]=5, transposed[2][1]=6

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

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：3x3方阵int[][]matrix1={{1,2,3},{4,5,6},{7,8,9}};int[][]result1=solution.transpose(matrix1);System.out.println("Test 1: "+Arrays.deepToString(result1));// 输出: [[1,4,7],[2,5,8],[3,6,9]]// 测试用例2：2x3非方阵int[][]matrix2={{1,2,3},{4,5,6}};int[][]result2=solution.transpose(matrix2);System.out.println("Test 2: "+Arrays.deepToString(result2));// 输出: [[1,4],[2,5],[3,6]]// 测试用例3：3x2非方阵int[][]matrix3={{1,2},{3,4},{5,6}};int[][]result3=solution.transpose(matrix3);System.out.println("Test 3: "+Arrays.deepToString(result3));// 输出: [[1,3,5],[2,4,6]]// 测试用例4：单行矩阵int[][]matrix4={{1,2,3,4,5}};int[][]result4=solution.transpose(matrix4);System.out.println("Test 4: "+Arrays.deepToString(result4));// 输出: [[1],[2],[3],[4],[5]]// 测试用例5：单列矩阵int[][]matrix5={{1},{2},{3}};int[][]result5=solution.transpose(matrix5);System.out.println("Test 5: "+Arrays.deepToString(result5));// 输出: [[1,2,3]]// 测试用例6：1x1矩阵int[][]matrix6={{42}};int[][]result6=solution.transpose(matrix6);System.out.println("Test 6: "+Arrays.deepToString(result6));// 输出: [[42]]// 测试用例7：包含负数的矩阵int[][]matrix7={{-1,-2},{-3,-4},{-5,-6}};int[][]result7=solution.transpose(matrix7);System.out.println("Test 7: "+Arrays.deepToString(result7));// 输出: [[-1,-3,-5],[-2,-4,-6]]}