假设A和B是两个大小相同的数组，每个数组都没有重复成员。有什么有效的算法吗
1.决定A和B是否有相同的成员
2.如果1的答案为真，则决定将A带到B的置换的符号（f（A[i]）==f（B[i]））？
谢谢。
您可以使用哈希表找到将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）预期时间。
现在你只需要找到排列的符号。你至少有两个选择：
- 计数反转次数这在O（n log n）或更好的情况下肯定是可能的
- 循环分解这只需要线性时间
事实上，您可以直接在输入数组上使用循环分解，这将产生一个漂亮而简短的实现。
一个有效的算法（O（n^2））如下（假设两个数组中都没有重复）。
bool same;
for(int i=0; i<L; i++)
{
same = false;
for(int j=0; j<L; j++) // see if A[i] is in B
if(A[i]==B[j])
{
same = true; // found A[i] in B
break;
}
if(!same) // A[i] was not found in B
break;
}
这里L是数组的长度。在循环结束时，如果数组包含相同的元素，则same将为true，否则为false。希望这能有所帮助。
PS：如果数组包含重复项，则此代码告诉A是否包含在B中。但是，您可以交换A和B的角色，并决定B是否包含在A中。如果B中包括的A和A中包含的B两者，则A=B。
这是一个一般的算法问题，还是您要求一个特定的（基于语言的）实现？
对于问题#1，只需对O(nlog(n))中的每个数组进行排序，然后比较O(n)中的数组。
如果输入值的范围不是很大，那么您可以使用直接哈希表，并在O(n)中执行排序阶段，从而将总体复杂性从O(nlog(n))降低到O(n)。
在Java中，您可以使用HashMap实例来实现这一点。我不确定这个类的内部实现，但对于大范围的输入值，它可能会达到相同的性能甚至。
对于问题#2，由于不存在重复元素，因此排列的总数为n!。
您可以计算整个排列组中每个阵列的排列ID，然后使用您计算的ID对来唯一标识两个阵列之间的映射。
例如，假设A = {3,2,1,4}和B = {4,1,3,2}。
排列的总数是24，因此每个排列可以映射到0到23之间的ID：
1,2,3,4 ==> 0
1,2,4,3 ==> 1
1,3,2,4 ==> 2
1,3,4,2 ==> 3
1,4,2,3 ==> 4
1,4,3,2 ==> 5
2,1,3,4 ==> 6
2,1,4,3 ==> 7
2,3,1,4 ==> 8
2,3,4,1 ==> 9
2,4,1,3 ==> 10
2,4,3,1 ==> 11
3,1,2,4 ==> 12
3,1,4,2 ==> 13
3,2,1,4 ==> 14
3,2,4,1 ==> 15
3,4,1,2 ==> 16
3,4,2,1 ==> 17
4,1,2,3 ==> 18
4,1,3,2 ==> 19
4,2,1,3 ==> 20
4,2,3,1 ==> 21
4,3,1,2 ==> 22
4,3,2,1 ==> 23
- 阵列
A映射到ID 14 - 阵列
B映射到ID 19 - 映射f（A，B）=（14,19）
如果希望此函数生成一个值，则可以使用n!*id1+id2而不是id1,id2。
或者，您可以定义映射函数f（A，B）以返回索引更改的数组。
例如，假设A = {3,2,1,4}和B = {4,1,3,2}。
- 索引0处的元素移动到索引2，因此索引更改为+2
- 索引1处的元素移动到索引3，因此索引更改为+2
- 索引2处的元素移动到索引1，因此索引更改为-1
- 索引3处的元素移动到索引0，因此索引更改为-3
因此，f({3,2,1,4},{4,1,3,2})应该返回数组{2,2,-1,-3}。