python - 对无序连续整数进行排序的最小交换

Question

给定一个由连续整数组成的无序数组[1, 2, 3, ..., n]，没有任何重复项。您可以交换任意两个元素。您需要找到按升序对数组进行排序所需的最小交换次数。我得到的代码在一些测试用例中超时了。有什么办法可以优化代码吗？

我的代码如下:

def minimumSwaps(arr):
    lst=[ele+1 for ele in range(len(arr))]
    cnt=0
    for i in range(len(arr)):
        if(lst[i]!=arr[i]):
            k=arr.index(lst[i])
            arr[i],arr[k]=arr[k],arr[i]
            cnt=cnt+1
    return cnt

Answer 1

您实际上并不需要生成引用列表lst，因为您应该知道arr中的n应该位于索引n-1 为升序。此外，执行 k=arr.index(lst[i]) 需要 O(n) 时间进行搜索，这是完全没有必要的。这是我的解决方案:

def minimumSwaps(arr):
    total_swaps = 0
    start = 0
    while start < len(arr):
        if arr[start] == start + 1:
            start += 1
            continue
        arr[arr[start] - 1], arr[start] = arr[start], arr[arr[start] - 1]
        total_swaps += 1
    return total_swaps

如果我猜对了，这是 Hackerrank 上的一个问题，这是我通过测试时的解决方案。 :P

该算法从位置一开始，将光标下的项目直接交换到正确的位置。当正确的项目交换到此位置时，它将光标增加到下一个项目并重复该过程。

这比顺序遍历数组、将正确的项目交换到每个位置更有效，因为您不必准确计算出正确的项目位于列表尾部的位置。