algorithm - 如何确定两个有序集合之间排列的符号？

Question

假设 A 和 B 是两个相同大小的数组，并且每个数组都没有重复的成员。有没有什么高效的算法可以

1.判断A和B是否有相同的成员

2.如果 1 的答案为真，确定将 A 带到 B(f(A[i])==f(B[i])) 的排列的符号？

谢谢。

Answer 1

您可以使用哈希表找到将 A 转换为 B 的排列:

pos = hash table (value -> position) of B
perm = []
for a in A:
    if a not in pos: return "not the same!"
    perm += [pos[a]]

这部分需要 O(n) 的预期时间。

现在您只需找到排列的符号。您至少有两个选择:

• Count the number of inversions这绝对有可能在 O(n log n) 或更好
• Cycle decomposition这只需要线性时间

事实上，您可以直接在输入数组上使用循环分解，这将产生一个不错且简短的实现。