给定一个随机顺序的整数数组,你必须找到最小数量的交换,将其转换为循环排序数组

Question

如果以随机顺序给出数组,则必须输出转换为循环排序数组所需的最小交换数.

例如,给出的阵列是3 5 4 2 1

所以第一次交换将是5 < - > 4结果:3 4 5 2 1秒交换将是2 < - > 1结果:3 4 5 1 2(最终)

输出:2

我无法理解这个问题背后的逻辑.

添加更多: 只能在相邻元素之间进行交换,数字在1到N之间

Answer 1

好吧,不知道它是否是最好的算法,但我可以想到一个O(n ^ 2)解决方案:

首先,忽略循环数组的可能性.让我们解决一个更简单的问题:对数组进行排序的最小交换次数是多少.

这里要小心,因为这不是排序算法.基于比较的排序算法至少会出现最坏情况O(n log n).在这个问题中,您需要的最大交换次数是n.

为什么？因为它是您可以实现的最大排列周期大小.您需要的最小交换数量恰好是排列周期大小减去1.我的意思是你可以将数组的任何排列表示为置换周期,例如:

3 2 1 4 5 - > (2)(4)(5)(1 3)

对于大小为1的排列周期,您不需要任何交换.对于大小为2的置换周期,您只需要1个交换.这可以扩展为:

2 3 4 5 1 - > (1 2 3 4 5)

忽略这个数组已经是循环排序的,这个数组是完全混乱的.为了正常排序,我需要4个交换,基本上将1移动到它的正常位置.

计算置换周期非常简单,只需跟踪数字到数组排序的位置即可.使用前面的例子

3 2 1 4 5

• 开始于A[0];
• 因为A[0]==3,3将是排序数组中的第3个元素,所以跟随到第3个位置;

• 因为A[2]==1,1将是......,接着是第1位.因为我们已经在这里,我们有一个2的周期 ;

• 在下一个未访问的位置再次开始(1)

• A[1]==2是在正确的位置,所以我们不需要做任何事情,这里我们有一个1号的周期.

• 等等......

这个算法是O(n),但是因为我们需要在每个可能的位置开始这个数组(因为它是圆形的),我们会这样做n次,因此,整个算法是O(n ^ 2).

更新; 一些python代码来显示我的算法:

def offset_swaps(A, S, offset):
    visited = [False]*len(A)
    swaps = 0

    for i in xrange(len(A)):
        if visited[i]: continue

        cycle, current = 0, i
        while not visited[current]:
            cycle += 1
            visited[current] = True
            current = (S[A[current]] + offset) % len(A)

        swaps += cycle - 1

    return swaps       

def number_of_swaps(A):
    S = {x:i for i,x in enumerate(sorted(A))}
    min_swaps = len(A)
    for i in xrange(len(A)):
        min_swaps = min(min_swaps, offset_swaps(A, S, i))
    return min_swaps

print number_of_swaps((3, 5, 4, 2, 1))

Answer 2

我认为这里的方法应该是 - 将所有数字排序到一个辅助数组中。然后，对于每个循环移位，计算将原始数组转换为该循环移位所需的交换次数。选择其中最小的一个。

要找到将数组 A 转换为数组 B 所需的最少交换次数，只需计算交换值的数量（即，A 中的值 a 位于值 b 的左侧，但在数组 B 中反之亦然）。这个问题相当于计算给定数组中的反转，并且可以再次使用修改后的合并排序来解决O(n*log(n))。

我的方法的复杂性是O(n^2*log(n))（因为您对大小为 n 的数组的所有循环移位进行合并排序）。

我想不出更快的解决方案来解决您的问题。