最小交换次数

任意两个元素可交换

问题描述： 给出一个具有N个不同值的数组A[]，找出将数组排序所需的最小交换次数。

解法一：交换法

遍历数组[1 5 4 3 2]，

1在正确的位置上，跳过；

5不在正确的位置上，将其与2交换。2交换到了排序后的正确位置，停止；

4不在正确的位置上，将其与3交换。3交换到了排序后的正确位置，停止；

算法结束，共交换两次。
复制代码

def solution(list):
    # 将元素从小到大排序好
    sorted_list = sorted(list)
    number = 0
    for i in range(len(list) - 1):   #将数组及排序数组进行交换 记录次数
        if sorted_list[i] != list[i]:
            for j in range(i+1, len(list)):
                if sorted_list[i] == list[j]:
                    
                    list[i],list[j] = list[j],list[i]
                    number += 1
    return number
复制代码

解法二：循环节

在一次操作中，把该次操作的所有元素都交换到正确位置上的所有操作形成的环，也就是循环节。

• 例子中，有三个循环节，分别为【1】【5, 2】;【4, 3】

//假设数组的循环节个数为lops 最小交换次数min_swaps = len(A) - lops

def min_swaps(nums):
    # mp记录排序后数值应在的正确位置
    mp = {}
    sort_nums = sorted(nums)
    for i in range(len(sort_nums)):
        mp[sort_nums[i]] = i

    # 循环节个数
    lops = 0
    # 该位置的数是否被访问过
    flags = []
    for i in range(len(nums)):
        flags.append(False)
    for i in range(len(nums)):
        if not flags[i]:
            j = i
            while not flags[j]:
                flags[j] = True
                # j是当前值应在的正确位置
                j = mp[nums[j]]
            lops += 1
    return len(nums) - lops

复制代码