Python程序：查找排序序列所需的交换次数

假设我们有一个包含不同数字的列表；我们必须找到按升序排序该列表所需的最小交换次数。

因此，如果输入类似于 nums = [3, 1, 7, 5]，则输出将为 2，因为我们可以交换 3 和 1，然后交换 5 和 7。

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

  • sort_seq := 对列表 nums 进行排序
  • table := 一个新的映射
  • 对于nums中的每个索引 i 和值 n：
    • table[n] := i
  • swaps := 0
  • 对于 i 从 0 到 nums 的大小：
    • n := nums[i]
    • s_n := sort_seq[i]
    • s_i := table[s_n]
    • 如果 s_n 不等于 n，则：
      • swaps := swaps + 1
      • nums[s_i] := n
      • nums[i] := s_n
      • table[n] := s_i
      • table[s_n] := i
  • 返回 swaps

让我们看下面的实现来更好地理解。

示例代码

在线演示

class Solution:
def solve(self, nums):
   sort_seq = sorted(nums)
   table = {}

   for i, n in enumerate(nums):
      table[n] = i
   swaps = 0
   for i in range(len(nums)):
      n = nums[i]
      s_n = sort_seq[i]
      s_i = table[s_n]

      if s_n != n:
         swaps += 1
         nums[s_i] = n
         nums[i] = s_n
         table[n] = s_i
         table[s_n] = i

      return swaps

ob = Solution()
nums = [3, 1, 7, 5]
print(ob.solve(nums))

输入

[3, 1, 7, 5]

输出

2

更新于: 2020年11月25日

1K+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告