java - 有效地反转Java中数组的排列

Question

好的，这是我的问题:

我用 Java 实现了一个算法，其中的一部分如下:问题是如何以有效的方式做我现在要解释的事情。

给定:长度为 n 的数组 a整数数组 perm，它是 [1..n]

的排列

现在我想使用数组 perm 确定的顺序排列数组 a，

即a=[a,b,c,d], perm=[2,3,4,1] ------> permutedA[b,c,d,a],

我发现我可以通过迭代数组来做到这一点:permutedA[i]=a[perm[i]-1]，(-1 因为 perm 中的排列索引以 1 而不是 0 开头)

现在我想对permutedA做一些操作...

现在我想做相反的置换操作。这是我不确定该怎么做的地方。注意 a 可以持有一个项目不止一次，即 a=[a,a,a,a]

现在我认为使用 Hashmap 而不是 perm 数组会有所帮助。但我不确定这是否是最好的方法。

Answer 1

你的意思是

ShuffledA[i] = a[perm[i]-1]

在你洗牌的时候你可以建立逆洗牌:

 inverseperm[perm[i]-1] = i + 1

构建

 inversePerm[4 1 2 3]

然后您将现有算法应用于 [b c d a] 产生原始 [a b c d]