算法设计题：设稀疏矩阵M(m×n)中有t个非零元素，用三元组表的方式存储。设计一个算法,计算矩阵M的转置矩阵N，且算法的时间复杂性为O(n+t)。算法用c++ (1)给出算法的基本思想。 (2)写出算法，并对算法中的关键步骤适当注释。 (3)给出算法的时间和空间复杂度。

算法设计基本思路：

(1) 因为原始矩阵M是非对称的稀疏矩阵，其转置矩阵N将拥有相同的非零元素个数t。为了保持时间复杂度为O(n+t)，我们可以遍历一次M的所有非零元素，在遍历时同时构造转置矩阵N的对应行。这样，对于每个非零元素(i, j)，我们将它添加到N的j列上。

// 假设sparseTripleTable[]是一个存储稀疏矩阵M的三元组表，结构如下
struct SparseTriple {
    int row, col, value;
};

void transposeSparseMatrix(SparseTriple sparseTripleTable[], int m, int n, int t, SparseTriple* transposedTripleTable, int& tTransposed) {
    // 初始化转置矩阵的计数器
    tTransposed = 0;

    // 遍历原矩阵M的非零元素
    for (int i = 0; i < t; i++) {
        int newRow = sparseTripleTable[i].col; // 保存原矩阵中非零元素所在的新行
        int newCol = sparseTripleTable[i].row; // 保存原矩阵中非零元素所在的新列

        // 将当前非零元素添加到转置矩阵N的对应位置，并更新计数器
        transposedTripleTable[tTransposed++] = {newRow, newCol, sparseTripleTable[i].value};
    }
}

(2) 关键步骤注释：
- `sparseTripleTable[i].col` 表示原矩阵M的第i个非零元素所在的列，转换到转置矩阵N时变成了新的行。
- `sparseTripleTable[i].row` 变成了新的列，因为我们需要将这个值作为新行的索引。

(3) 时间复杂度分析：
- 我们遍历了所有的t个非零元素，以及每个非零元素需要常量时间进行插入，所以总时间复杂度为O(t)。
- 对于空间复杂度，我们创建了一个新的三元组数组来存储转置矩阵，最坏情况下（所有非零元素都在对角线上），需要的空间也是O(n)，因为会生成n个元素。但由于原始矩阵的稀疏特性，实际平均空间复杂度更接近O(t)。总体来说，如果t << min(m, n)，则空间效率较高。