矩阵原地转置，空间复杂度为O(1)(暂时先保存下来)

本文介绍了一种不使用额外空间的矩阵转置算法实现方法。通过计算矩阵元素的前后位置关系，实现了矩阵数据的有效循环移动，最终完成转置操作。文章包含完整的C++代码示例，并演示了如何对一个矩阵进行转置。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include<iostream>
using namespace std;
 
/* 后继 */
int getNext(int i, int m, int n)
{
    return (i%n)*m + i/n;
}
 
/* 前驱 */
int getPre(int i, int m, int n)
{
    return (i%m)*n + i/m;
}
 
/* 处理以下标i为起点的环 */
void movedata(int *mtx, int i, int m, int n)
{
    int temp = mtx[i];  // 暂存
    int cur = i;       // 当前下标
    int pre = getPre(cur, m, n);
    while(pre != i)
    {
        mtx[cur] = mtx[pre];
        cur = pre;
        pre = getPre(cur, m, n);
    }
    mtx[cur] = temp;
}
 
/* 转置，即循环处理所有环 */
void transpose(int *mtx, int m, int n)
{
    for(int i=0; i<m*n; ++i)
    {
        int next = getNext(i, m, n);
        while(next > i) // 若存在后继小于i说明重复
            next = getNext(next, m, n);
        if(next == i)   // 处理当前环 
            movedata(mtx, i, m, n);
    }
}
 
/* 输出矩阵 */
void print(int *mtx, int m, int n)
{
    for(int i=0; i<m*n; ++i)
    {
        if((i+1)%n == 0)
            cout << mtx[i] << "\n";
        else
            cout << mtx[i] << " ";
    }
}
 
/* 测试 */
int main()
{
    int matrix[4*2] = {1,2,3,4,5,6,7,8};
    cout << "Before matrix transposition:" << endl;
    print(matrix, 4, 2);
    transpose(matrix, 4, 2);
    cout << "After matrix transposition:" << endl;
    print(matrix, 2, 4);
    return 0;
}