寻找无需O(n)额外内存的置换循环分解算法（用于原地矩阵转置）

这确实是原地矩阵转置里的一个关键问题——既要找到置换循环的起始点，又不想用O(hw)的标记数组占用内存，完全理解你的需求！

首先，我们先明确你提到的置换本质：s(i) = (i//w) + (i%w)*h 其实是把原h×w矩阵的行优先索引，映射到转置后w×h矩阵的行优先索引，这个置换的循环结构决定了原地转置时需要交换的元素组。

方法一：基于循环最小元素的无标记遍历 #

核心思路是：每个循环有且仅有一个最小元素，我们只需要遍历所有索引，当且仅当前索引是它所在循环的最小元素时，将其加入cycles数组。这样就不需要额外的visited数组来标记已处理元素。

具体代码如下：

std::vector<size_t> cycles;
const size_t total = h * w;

for (size_t i = 0; i < total; ++i) {
    size_t current = i;
    bool is_smallest = true;
    
    // 沿着置换链遍历，检查是否存在比i更小的元素
    do {
        if (current < i) {
            is_smallest = false;
            break; // 发现更小的元素，说明这个循环已经被处理过了
        }
        current = (current / w) + (current % w) * h;
    } while (current != i);
    
    if (is_smallest) {
        cycles.push_back(i);
    }
}

原理说明

• 对于每个索引i，我们沿着置换的链条走一遍，只要中途遇到比i小的元素，就说明这个循环的起始点已经被更小的那个元素处理过了，直接跳过。
• 只有当遍历完整个循环都没找到比i小的元素时，i就是这个循环的最小元素，也就是我们需要的起始点。

优缺点

• 优点：完全不需要额外标记数组，实现简单直观。
• 缺点：最坏情况下时间复杂度是O(n²)（比如当整个置换是一个大循环时，每个元素都要遍历整个循环才能判断）。这种情况在h和w互质且几乎没有自循环元素时会出现。

方法二：利用数论性质的O(n)时间优化 #

如果想要在O(n)时间内完成，我们可以利用置换的数学性质来直接定位循环起始点，避开遍历整个循环的开销。

首先，先找出所有自循环元素（即满足s(i)=i的元素）：
自循环的条件是(i//w) + (i%w)*h = i。设i对应的二维坐标为(r, c)（r = i//w，c = i%w），代入得：
c*h + r = r*w + c → c*(h-1) = r*(w-1)

设d = gcd(h-1, w-1)，h-1 = d*a，w-1 = d*b（此时gcd(a,b)=1），方程简化为c*a = r*b。由于a和b互质，b必须整除c，a必须整除r。设c = b*k，r = a*k，其中k的取值要满足0 ≤ r < h且0 ≤ c < w，即k < min(h/a, w/b)。这些k对应的i = r*w + c = k*(a*w + b)就是所有自循环元素，直接加入cycles。

接下来处理非自循环的循环：
对于非自循环元素，我们可以利用置换的循环周期性质。当h和w的最大公约数为g = gcd(h, w)时，整个置换可以分解为g组独立的循环，每组循环的元素满足i ≡ k mod g（k从0到g-1）。对于每组k，我们只需要找到该组中最小的非自循环元素作为起始点加入cycles即可。

具体代码实现需要结合gcd计算，这里给出核心逻辑：

#include <algorithm> // for gcd (C++17+)

std::vector<size_t> cycles;
const size_t total = h * w;
const size_t g = std::gcd(h, w);
const size_t d = std::gcd(h-1, w-1);
const size_t a = (h-1)/d;
const size_t b = (w-1)/d;

// 先添加所有自循环元素
for (size_t k = 0;; ++k) {
    size_t r = a * k;
    size_t c = b * k;
    if (r >= h || c >= w) break;
    size_t i = r * w + c;
    cycles.push_back(i);
}

// 添加非自循环的循环起始点
std::vector<bool> is_self(total, false);
for (size_t i : cycles) is_self[i] = true; // 这里用了小空间，远小于O(total)

for (size_t k = 0; k < g; ++k) {
    // 找该组中最小的非自循环元素
    for (size_t i = k; i < total; i += g) {
        if (!is_self[i]) {
            cycles.push_back(i);
            break;
        }
    }
}

原理说明

• 自循环元素通过解方程直接生成，无需遍历。
• 非自循环元素按mod g分组，每组对应一个独立循环，只需找到每组第一个非自循环元素作为起始点即可。
• 这里用了一个小的is_self数组来标记自循环元素，但其大小是自循环元素的数量，远小于h*w，内存开销可以忽略。

优缺点

• 优点：时间复杂度O(n)，内存开销极小。
• 缺点：需要理解置换的数论性质，实现相对复杂。

两种方法都能生成你需要的cycles数组，具体选择取决于你的场景：如果矩阵规模不大，方法一足够简单好用；如果处理大规模矩阵，方法二更高效。

内容的提问来源于stack exchange，提问作者thebensky