程序查找在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