Python程序:计算将一个列表转换为另一个列表所需的交换次数?


假设我们有两个数字列表 L1 和 L2,每个列表的长度为 n,每个值在其列表中都是唯一的,并且值在 1 到 n 的范围内,我们需要找到将 L1 转换为 L2 所需的最少相邻交换次数。

因此,如果输入类似于 L1 = [0, 1, 2, 3] L2 = [2, 0, 1, 3],则输出将为 2,因为我们可以交换 1 和 2,L1 将变为 [0, 2, 1, 3],然后交换 0 和 2,L1 将变为 [2, 0, 1, 3],这与 L2 相同。

为了解决这个问题,我们将遵循以下步骤

  • ans := 0

  • 对于 L2 中的每个 req,执行以下操作

    • i := req 在 L1 中的索引

    • 从 L1 中删除第 i 个元素

    • ans := ans + i

  • 返回 ans

让我们看看以下实现以更好地理解

示例

 在线演示

class Solution:
   def solve(self, L1, L2):
      ans = 0
      for req in L2:
         i = L1.index(req)
         L1.pop(i)
         ans += i
      return ans

ob = Solution()
L1 = [0, 1, 2, 3]
L2 = [2, 0, 1, 3]
print(ob.solve(L1, L2))

输入

[0, 1, 2, 3],[2, 0, 1, 3]

输出

2

更新于: 2020年11月10日

354 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告