无额外内存的数组元素索引式重定位函数设计及覆盖问题求解

你的问题根源在于操作顺序错误导致原始值被提前覆盖：当某个目标索引同时是后续操作的源索引时，先执行的写入操作会破坏后续需要的原始数据。要在尽量不使用大规模辅助内存的前提下解决，我们可以通过拓扑排序处理依赖关系+循环链单独处理的方式，保证所有操作都基于原始数组的值执行。

核心思路 #

1. 构建依赖关系：如果操作A的目标是操作B的源，那么B必须在A之前执行（B需要原始的源值，A会修改该值）。我们通过邻接表和入度数组记录这种依赖。
2. 拓扑排序执行无依赖操作：优先执行没有前置依赖的操作，确保这些操作使用的源值不会被后续操作修改。
3. 处理循环依赖链：对于形成闭环的依赖链（如A的目标是B的源，B的目标是A的源），用单个临时变量保存链的起始原始值，依次完成赋值，避免中间覆盖。

实现代码（C++模板版，支持任意类型） #

#include <vector>
#include <queue>

template<typename T>
void Duplicate(T Array[], const int Dst_Indexes[], const int Src_Indexes[], int Count) {
    // 邻接表：adj[i] 存储所有依赖操作i的后续操作
    std::vector<std::vector<int>> adj(Count);
    // 入度数组：记录每个操作需要等待多少前置操作完成
    std::vector<int> in_degree(Count, 0);

    // 构建依赖关系
    for (int i = 0; i < Count; ++i) {
        for (int j = 0; j < Count; ++j) {
            // 若操作j的目标是操作i的源，说明i必须在j之前执行，j依赖i
            if (Dst_Indexes[j] == Src_Indexes[i]) {
                adj[i].push_back(j);
                in_degree[j]++;
            }
        }
    }

    // 初始化队列：入度为0的操作无前置依赖，可先执行
    std::queue<int> q;
    for (int i = 0; i < Count; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    // 拓扑排序执行操作
    while (!q.empty()) {
        int idx = q.front();
        q.pop();
        // 执行当前复制操作
        Array[Dst_Indexes[idx]] = Array[Src_Indexes[idx]];
        // 更新后续操作的入度，完成前置依赖则加入队列
        for (int next_idx : adj[idx]) {
            if (--in_degree[next_idx] == 0) {
                q.push(next_idx);
            }
        }
    }

    // 处理剩余的循环依赖链
    std::vector<bool> visited(Count, false);
    for (int i = 0; i < Count; ++i) {
        if (visited[i] || in_degree[i] == 0) continue;

        int current_idx = i;
        // 保存循环链起始位置的原始值
        T temp = Array[Src_Indexes[current_idx]];
        while (!visited[current_idx]) {
            visited[current_idx] = true;
            int dst = Dst_Indexes[current_idx];
            // 找到链中的下一个操作
            int next_idx = -1;
            for (int j = 0; j < Count; ++j) {
                if (!visited[j] && Src_Indexes[j] == dst) {
                    next_idx = j;
                    break;
                }
            }
            // 完成当前位置的复制，并传递原始值
            if (next_idx != -1) {
                T next_temp = Array[Src_Indexes[next_idx]];
                Array[dst] = temp;
                temp = next_temp;
            } else {
                Array[dst] = temp;
            }
            current_idx = next_idx;
        }
    }
}

示例验证 #

针对你给出的测试用例：

• 初始数组：Array = {23, 67, 167, 9, 5690}
• Src_Indexes = {4, 0}，Dst_Indexes = {0, 2}，Count = 2

执行流程：

1. 依赖关系构建：操作2（索引1）的源是0，操作1（索引0）的目标是0，因此操作0依赖操作1，in_degree[0] = 1，in_degree[1] = 0。
2. 拓扑排序先执行操作1：Array[2] = Array[0]，数组变为{23, 67, 23, 9, 5690}。
3. 操作0的入度减为0，执行操作0：Array[0] = Array[4]，数组变为{5690, 67, 23, 9, 5690}，与预期结果一致。

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