c++ - 用 O(1) 空间重新映射数组

Question

很抱歉，我不确定这个问题叫什么类型，我们就叫它“Remapping”吧，描述如下:给定一个目标字符数组，比如 A[]，您必须直接操作 A。以及一个重新映射索引数组 index[]，其中包含应重新分配值的索引。例如，给定 A[] = {a, b, c, d, e}，index[] = {2,4,3,0,1}。所以index[0] = 2，这意味着在操作之后，A[0]中的值必须是A[2]，A[1]在A[4]中，等等。我知道如果我们有另一个数组，这个问题就非常容易了:

vector<char> myarr = vector<char>(A.size());
for (int i = 0; i < myarr.size(); i++)
    myarr[i] = A[index[i]];

// myarr is the answer.

但是如果我只允许 O(1) 空间怎么办？感谢您分享您的意见。

哦，顺便说一句，如果我有任何语法错误，请纠正我:“P

Answer 1

这个问题可以通过交换一对具有常量内存的值来解决，以便就地生成结果。虽然不是直接重复，但在 this question 中讨论了该问题.