在Python中寻找排序所需的最小交换次数的程序

假设我们有一个不同数字的列表；我们必须找到将列表按递增顺序排序所需的最小交换次数。

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

要解决这个问题，我们将按以下步骤进行：

sort_seq := 对列表nums进行排序
table := 一个新的映射
对于nums中的每个索引i和值n，做如下操作：
- table[n] := i
swaps := 0
对于范围从0到nums大小的i，做如下操作：
- 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
返回交换次数

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

更多Python相关文章，请阅读：Python 教程

示例代码

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))