最小交换次数

任意两个元素可交换

问题描述: 给出一个具有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

复制代码
全部评论

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 11:30
找工作7个月,投了7000封,3段世界五百强实习,才有一个offer,牛油们肯定比我强吧
码农索隆:不对不对不对,实习经历这么厉害,简历也没少投,问题出在哪呢
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务