Python找出最小排序次数

>>最全面的Java面试大纲及答案解析(建议收藏)  

对于一组由从1开始的连续的正整数组成的无序序列,我们要以升序的方式对它们进行排列,允许任意两个书交换位置,要求给出最小的交换次数。
由于有从1开始的连续的正整数这个限定条件在,这个问题事实上被大大简化了。
首先考虑到对于一个较坏的情况,如[5,4,3,2,1],如果用冒泡排序法,就要交换10次才能完成。
但事实上,我们完全可以这样交换:数字5应当位于位置5(在编写代码时不要忘记索引从0开始,所以这里其实是索引4),我们将它与位置5的元素交换,以此类推,对于这个序列,只需要两次交换就可以完成!这种排序方式的思想我觉得有点近似于圈排序(Cycle Sort)[1]

列出代码:

 1def minimumSwaps(arr):
2    swaps = 0
3
4    for i in range(len(arr)):
5        if arr[i] == i + 1:
6            continue
7        else:
8            position = arr.index(i+1)
9            arr[i], arr[position] = arr[position], arr[i]
10            swaps += 1
11
12    return swaps
  • 我们忽略索引与实际值相同的想,需要注意的是,索引是从0开始的,需要加一才能和实际值一致,所以这里要使用if arr[i] == i + 1

  • 对于索引与值不同的情况,我们找出该索引本来需要的值现在的位置,通过arr.index(i+1)来寻找。list.index()方法可以用来寻找一个元素在列表中的索引。

  • 接着实现交换,并用swaps变量来存储交换次数。

[1]:Cycle Sort

欢迎扫描下方二维码关注公众号:

Python找出最小排序次数


原文始发于微信公众号(公子政的宅日常):Python找出最小排序次数