程序查找在python中对序列进行排序所需的交换次数

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

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

为了解决这个问题，我们将按照以下步骤操作：

• sort_seq：=对列表中的数字进行排序

• 表格：=新map

• 对于以数字为单位的每个索引i和值n

• table [n]：= i

• 掉期：= 0

• 对于范围从0到nums的i，执行

• 掉期：=掉期+ 1

• nums [s_i]：= n

• nums [i]：= s_n

• 表[n]：= s_i

• table [s_n]：= i

• n：= nums [i]

• s_n：= sort_seq [i]

• s_i：=表格[s_n]

• 如果s_n与n不相同，则

• 回报互换

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

范例程式码

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