数一共有几个环,每个环可以减少一次交换(有n个数的环交换次数为n-1),则只有一个环的时候交换次数最多为n-1。环最多的情况是本身就有序。
此题来说5次有两个环,至少6次只有一个环。
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
次数最少的交换方法是:每次两两交换至少要使一个字符到达最终位置。
第一次交换a,g结果为:abfcdge
第一次交换c,f结果为:abcfdge
第一次交换f,d结果为:abcdfge
第一次交换e,f结果为:abcdegf
第一次交换g,f结果为:abcdefg
完成,一共交换了5次
上面的交换中,由于b正好在最终位置,因此省去了一次交换
任给一个自由a--g这7个字母组成的排列,最坏情况需要交换7-1=6次
这种最坏情况是每个字符都需要交换一次来达到最终位置,最后一次交换使的两个字符同时到达最终位置。N个字符最坏情况需要至少N-1次交换