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

  • Z时代
  • 2024-01-10
  • 分类：综合

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

因此，如果输入类似于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

以上是 程序查找在python中对序列进行排序所需的交换次数 的全部内容， 来源链接： utcz.com/z/350142.html

回到顶部