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

  • Z时代
  • 2024-01-10
  • 分类：问答

我们给了两个小写拉丁字母序列。它们的长度均相同，并且具有相同数量的给定类型的字母（第一个字母与第二个字母具有相同数量的t，依此类推）。我们需要找到将第一个序列转换为第二个序列所需的最小交换次数（

“交换”是指更改两个 字母 的顺序 ）。我们可以安全地假设每两个序列可以相互转换。我们可以用蛮力来做到这一点，但是序列太长了。

序列的长度（至少2个，最大999999），然后是两个序列。

一个整数，表示序列变得相同所需的交换次数。

{5，aaaaa，aaaaa}应该输出{0}，

{4，abcd，acdb}应该输出{2}。

我想到的第一件事是冒泡。我们可以简单地对排序每个交换的序列进行冒泡排序。问题是：a）是O（n ^

2）最坏的情况b）我不确信在每种情况下它都会给我最小的数字…即使是优化的冒泡现象也似乎并不能解决问题。我们可以实施鸡尾酒疗法来解决乌龟的问题-

但这会给我最好的表现吗？也许有更简单/更快的东西？

这个问题也可以表述为：

回答：

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

让Q[ s2[i] ] = the positions character s2[i] is on in s2。让P[i] = on what

position is the character corresponding to s1[i] in the second string。

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

    1234
s1: abcd
s2: acdb
Q: 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)。

以上是 计算将一个排列转换为另一个排列所需的相邻交换 的全部内容， 来源链接： utcz.com/qa/406789.html

回到顶部