当前位置：首页 > article >正文

c/c++蓝桥杯经典编程题100道（14）矩阵转置

article 2025/2/10 19:54:36

矩阵转置

->返回c/c++蓝桥杯经典编程题100道-目录

矩阵转置

一、题型解释

二、例题问题描述

三、C语言实现

解法1：使用额外空间（难度★）

解法2：原地转置（仅限方阵，难度★★）

四、C++实现

解法1：使用STL容器（难度★☆）

解法2：原地转置优化（方阵，难度★★）

五、总结对比表

六、特殊方法与内置函数补充

1. C语言中的变长数组（VLA）

2. C++的 swap 函数

3. 并行化优化

一、题型解释

矩阵转置是将矩阵的行和列互换的操作。常见题型：

基础转置：将任意大小的矩阵行列互换（如 3x2 转为 2x3）。
原地转置：在不使用额外空间的情况下转置方阵（仅限行数等于列数的矩阵）。
特殊矩阵转置：对称矩阵的转置（转置后与原矩阵相同）。

二、例题问题描述

例题1：输入 3x3 矩阵：

1 2 3  
4 5 6  
7 8 9

输出转置结果：

1 4 7  
2 5 8  
3 6 9

例题2：输入 2x3 矩阵：

1 2 3  
4 5 6

输出转置结果：

1 4  
2 5  
3 6

例题3：输入对称矩阵：

1 2 3  
2 4 5  
3 5 6

输出转置结果与原矩阵相同。

三、C语言实现

解法1：使用额外空间（难度★）

通俗解释：

像抄写座位表一样，将原矩阵的行列互换，写入新矩阵。

#include <stdio.h>

void transpose(int rows, int cols, int src[][cols], int dest[][rows]) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            dest[j][i] = src[i][j]; // 行列互换
        }
    }
}

int main() {
    int src[2][3] = {
  
  {1, 2, 3}, {4, 5, 6}};
    int dest[3][2]; // 转置后为3x2
    
    transpose(2, 3, src, dest);
    
    // 打印结果
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 2; j++) {
            printf("%d ", dest[i][j]);
        }
        printf("\n");
    }
    // 输出：
    // 1 4
    // 2 5
    // 3 6
    return 0;
}

代码逻辑：

双重循环遍历原矩阵：外层循环行，内层循环列。
行列互换：将 src[i][j] 赋值给 dest[j][i]。
存储结果：需提前定义目标矩阵 dest，其大小为 cols x rows。

解法2：原地转置（仅限方阵，难度★★）

通俗解释：

像翻转书页一样，直接在原矩阵上交换元素（仅适用于行数等于列数的方阵）。

#include <stdio.h>

void transposeInPlace(int n, int matrix[][n]) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) { // 只遍历上三角
            // 交换 matrix[i][j] 和 matrix[j][i]
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

int main() {
    int matrix[3][3] = {
  
  {1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    transposeInPlace(3, matrix);
    
    // 打印结果
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
    // 输出：
    // 1 4 7
    // 2 5 8
    // 3 6 9
    return 0;
}

代码逻辑：

遍历上三角：避免重复交换（如 i=0,j=1 和 i=1,j=0 是同一个交换操作）。
元素交换：通过临时变量 temp 交换 matrix[i][j] 和 matrix[j][i]。

四、C++实现

解法1：使用STL容器（难度★☆）

通俗解释：

用动态数组（vector）实现任意大小的矩阵转置，像搭积木一样灵活操作。

cpp

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> transpose(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return {};
    int cols = matrix[0].size();
    
    vector<vector<int>> result(cols, vector<int>(rows)); // 定义目标矩阵
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            result[j][i] = matrix[i][j]; // 行列互换
        }
    }
    return result;
}

int main() {
    vector<vector<int>> matrix = {
  
  {1, 2, 3}, {4, 5, 6}};
    auto transposed = transpose(matrix);
    
    // 打印结果
    for (auto& row : transposed) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
    // 输出：
    // 1 4
    // 2 5
    // 3 6
    return 0;
}

代码逻辑：

动态矩阵定义：使用 vector<vector<int>> 支持任意大小的矩阵。
安全访问：检查原矩阵是否为空（rows == 0）。

解法2：原地转置优化（方阵，难度★★）

通俗解释：

直接在原矩阵上操作，仅遍历上三角区域，避免重复交换。

cpp

#include <iostream>
#include <vector>
using namespace std;

void transposeInPlace(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) { // 只遍历上三角
            swap(matrix[i][j], matrix[j][i]); // 使用swap函数
        }
    }
}

int main() {
    vector<vector<int>> matrix = {
  
  {1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    transposeInPlace(matrix);
    
    // 打印结果
    for (auto& row : matrix) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
    // 输出：
    // 1 4 7
    // 2 5 8
    // 3 6 9
    return 0;
}

代码逻辑：

使用 swap 函数：C++标准库函数，直接交换两个元素。
遍历优化：仅遍历上三角区域（j = i + 1），时间复杂度为 O(n²/2)。

五、总结对比表

方法	时间复杂度	空间复杂度	优点	缺点
额外空间转置	O(mn)	O(mn)	支持任意矩阵	需要额外空间
原地转置	O(n²)	O(1)	节省空间	仅限方阵
STL容器转置	O(mn)	O(mn)	灵活支持动态矩阵	依赖STL库