将列表顺序返回到旧索引

Question

我有一个int数组，存储列表的旧索引，我用它来恢复列表中的数据顺序

int[] oldindex = function();

数组的工作原理:在index-n处的oldindex数组的值包含了在操作前index-n处的数据所在的索引位置

例如，oldindex[0]包含当前数据在索引0处的旧索引。

我已经尝试切换数据以恢复顺序。例如，通过创建一个临时变量来存储索引n处的数据，然后将索引n处的数据替换为索引k处的数据，并将索引k处的数据替换为临时变量中的数据。不管我做错了还是没有，它都不能恢复数据顺序。

for(int i = 0; i < data.size();i++) {
String temp = data.get(i);
data.set(i, data.get(oldindex[i]));
data.set(oldindex[i], temp);
}

使用临时列表在返回数据之前复制和重新排序数据是有效的，但是对于大数据来说它占用了太多的内存。

是否有更有效的替代方法?

Answer 1

非常简化(朴素)的实现:

private static void order(String[] values, int[] old) {
assert values.length == old.length;
for (int i = 0; i < values.length; i++) {
var nextv = values[old[i]];
var nexti = old[old[i]];
while (nexti != old[nexti]) {
var tempv = values[nexti];
var tempi = old[nexti];
values[nexti] = nextv;
old[nexti] = nexti;
nextv = tempv;
nexti = tempi;
}
}
}

请将其视为伪代码/想法

样本数据输出:

start   values:   [D, G, C, E, H, A, F, J, I, B]
oldindex: [3, 6, 2, 4, 7, 0, 5, 9, 8, 1]
result values:    [A, B, C, D, E, F, G, H, I, J]
oldindex: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 2

您在某个位置'p'拾取元素并将其放置在新的正确位置oldindex[p]。但是，您不想覆盖该位置上的元素，因此需要将其复制到一个临时变量中。现在您需要为这个元素oldindex[oldindex[p]]找到正确的位置。您将它存储在那里，但首先将该位置的元素保存到一个临时变量中。您将继续查找元素的正确位置，并在将其覆盖到临时变量之前保存元素，直到返回到开始时的初始位置"p"。此时，您可以将临时变量存储到列表的位置'p'，而不必担心覆盖它，因为您已经将该元素移动到正确的位置。在这一点上，你已经完成了列表中所有元素的正确排序，这使得从索引'p'开始的一个完整的排列循环。现在你需要取下一个不包含在这个排列循环中的元素并从这个元素开始构造一个新的排列循环，以此类推。然而，您需要跟踪哪些元素已经在正确的位置，哪些不是。因此，您仍然需要一个与列表O(n)大小成比例的临时空间，它可以是布尔值数组。但是我还是建议不要担心引用占用的空间。