计算将一个排列转换为另一个排列所需的相邻交换

计算将一个排列转换为另一个排列所需的相邻交换

这是一个简单而有效的解决方案：

让

Q[ s2[i] ] = the positions character s2[i] is on in s2

。让

P[i] = on whatposition is the character corresponding to s1[i] in the second string

。

建立Q和P：

for ( int i = 0; i < s1.size(); ++i )    Q[ s2[i] ].push_back(i); // basically, Q is a vector [0 .. 25] of liststemp[0 .. 25] = {0}for ( int i = 0; i < s1.size(); ++i )    P[i + 1] = 1 + Q[ s1[i] ][ temp[ s1[i] ]++ ];

例：

    1234s1: abcds2: acdbQ: Q[a = 0] = {0}, Q[b = 1] = {3}, Q[c = 2] = {1}, Q[d = 3] = {2}P: P[1] = 1, P[2] = 4 (because the b in s1 is on position 4 in s2), P[3] = 2   P[4] = 3

P

具有

2

反转（

4 2

和

4 3

），所以这就是答案。

此解决方案是

O(n log n)

因为构建

P

和

Q

可以在其中完成，

O(n)

而归并排序可以计算中的反转

O(n log n)

。