如果数组是由于在随机顺序，你要输出转换成循环排序的数组需要交换的最小数量。

if an array is given in random order , you have to output the minimum number of swaps required to convert into cyclic sorted array.

例如。定的数组为3 5 4 2 1

e.g. array given is 3 5 4 2 1

所以第一个交换将是5℃; - > 4的结果：3 4 5 2 1 第二个交换将是2'; - > 1结果：3 4 5 1 2（最终）

so the first swap will be 5<-->4 result : 3 4 5 2 1 second swap will be 2<-->1 result : 3 4 5 1 2 (final)

输出：2

我不能够落后这个问题的逻辑。

i am not able to get the logic behind this problem.

补充一些： 交换相邻的元素和数字之间的唯一可能是范围1间到N

推荐答案

好了，不知道这是否是可用的最好的算法，但我认为澳（N ^ 2）解决方案：

Well, don't know if it is the best algorithm available, but I can think of a O(n^2) solution:

首先，忽略环状阵列的可能性。让我们来解决一个简单的问题：什么是掉期交易到一个数组排序的最少数量

First, ignore the possibility of the cyclic array. Let's solve a simpler problem: what is the minimum number of swaps to sort an array.

这里要小心，因为这不是关于排序算法。一个的比较为基础的排序算法将有一个最坏的情况下，至少 0的（N日志N）。在这个问题中，你需要互换的最大数量为 N 。

Be careful here, because this isn't about sorting algorithms. A comparation-based sorting algorithm would have a worst-case of at least O(n log n). In this problem, the maximum number of swaps you need is n.

为什么呢？因为它是最大的置换周期大小就可以实现。互换您所需要的最小数量是完全置换周期大小减一。我的意思是，你可以重新present阵列作为一个置换周期的任何排列，如：

Why? Because it's the maximum permutation cycle size you can achieve. The minimum number of swaps you need is exactly the permutation cycle size minus one. I mean you can represent any permutation of the array as a permutation cycle, e.g.:

3 2 1 4 5 - > （2）（4）（5）（1 3）

有关尺寸1的排列周期，你不需要任何的交换。对于大小为2的置换周期，则需要完全1互换。该秤为：

For the permutations cycles of size 1, you don't need any swap. For the permutation cycle of size 2, you need exactly 1 swap. This scales as:

2 3 4 5 1 - > （1 2 3 4 5）

忽略此阵已是循环排序，这个数组tottaly混乱。要正常进行排序的话，我就需要4互换，基本上移动1到正常的位置。

Ignoring this array is already cyclic-sorted, this array is tottaly messed. To sort it normally, I would need 4 swaps, basically moving the 1 to it's normal position.

计算置换周期为pretty的方便，它后面的数字到它应该是，如果阵列排序的只是一个问题。使用previous例子

Calculating the permutation cycles is pretty easy, it's just a matter of following the number to where it should be if the array was sorted. Using the previous examples

3 2 1 4 5

由于 A [2] == 1 ，1是......，下面为1号位。正如我们已经在那里在这里，我们有大小2 的周期; Starts at A[0]; Because A[0]==3, and 3 would be the 3rd element in sorted array, follows to 3rd position;

Because A[2]==1, and 1 would be..., follows to 1st position. As we were already there here we have a cycle of size 2;

重新开始在下次访问过的位置（1）

Starts again at next unvisited position (1)

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

A[1]==2 is in it's right position, so we don't need to do anything, here we have a cycle of size 1.

等等...

这个算法为O（n），但我们需要这样做启动在每一个可能的位置（因为它是圆形的），我们会做了N次，这样的阵列，整个算法为O（n ^ 2）。

This algorithm is O(n), but as we need to do this for the array starting in every possible position (because it is circular), we would do it n times, so, the entire algorithm is O(n^2).

更新;一些蟒蛇code，以显示我的算法：

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))