矩阵原地转置（时间换空间）

思路引入

参考在一维数组中进行循环位移：

a[]={1,2,3,4}，要将数组循环左移1位，下标循环：

与循环位移类似，以一个2x3矩阵为例，元素右下角数字为其在一维数组中的下标。

直接从矩阵来看，看不出什么下标规律，但是将其展开为一维数组，就能发现一些下标循环：

• 
• 
• (重复)
• (重复)
• (重复)
• 

因此，考虑用循环数组的思路来处理矩阵转置。

详细思路

后继下标计算

对于N*M原矩阵中(i,j)元素，其在转置矩阵中索引为(j,i)，前者在一维数组下标为i*M+j，后者为j*N+i。

找循环

从下标0开始遍历一维数组，根据后继下标的计算方法，循环进行移动，直到回到循环起点，如上例

两种思路循环去重

从上方例子中可知，一个循环中包含多个下标，因此既要遍历的循环，又不能重复循环位移。

• 空间换时间：维护一个vis数组，空间复杂度O(n*m)，时间复杂度O(n*m)，但是因为要求是原地转置，空间上不符合要求，因此该思路不合适。
• 时间换空间：因为对于重复的下标循环，只是起始下标不同，而循环次序相同，而且每一个循环中，下标均不同（除起始点和回路终点外），因此规定遍历的循环必须满足以下条件：循环起点必须在循环序列中最小（当然也可以规定最大，只是在找环时，下标循环需从大到小）。此时，空间复杂度O(1)（不包含存储原矩阵的开销），时间复杂度O((n*m)^2)。

​

代码

//
// Created by Zed on 2024/2/17.
//
#include <iostream>

using namespace std;
const int MAXN = 1e2 + 100;
const int INF = 1e7;
int a[MAXN * MAXN];

int getSuccessor(int i, int n, int m) {//获取后继下标
    int x = i / m;
    int y = i % m;
    return y * n + x;
}

void transposition(int *A, int n, int m) {
    int len = n * m;
    for (int i = 0; i < len; ++i) {
        int nex = getSuccessor(i, n, m);
        bool v = false;
        while (nex != i) {
            if (nex < i) {//已经遍历过
                v = true;
                break;
            }
            nex = getSuccessor(nex, n, m);
        }
        if (!v) {
            int cur = i;
            nex = getSuccessor(cur, n, m);
            int tmp = A[cur];
            while (nex != i) {
                swap(tmp, A[nex]);//tmp中存储循环中当前遍历的元素值
                nex = getSuccessor(nex, n, m);
            }
            swap(tmp, A[nex]);
        }
    }
}

int main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i < n * n; ++i) {
            cin>>a[i];
        }
        transposition(a,n,n);
        for (int i = 0; i < n; ++i) {
            cout<<a[i*n];
            for (int j = 1; j < n; ++j) {
                cout<<" "<<a[i*n+j];
            }
            cout<<endl;
        }
    }
    return 0;
}