Judgecode - Sort with swap（2）

Question

我见过的问题如下，任何人有一些想法呢？ http://judgecode.com/problems/1011

给定从0到n-1的整数排列，排序它们很容易。但是如果每次只能交换一对整数呢？

请计算的最小数量互换

Answer 1

一个经典的算法似乎是置换周期（https://en.wikipedia.org/wiki/Cycle_notation#Cycle_notation）。所需的交换次数等于元素总数减去循环次数。

例如：

1 2 3 4 5 
2 5 4 3 1 

Start with 1 and follow the cycle: 
1 down to 2, 2 down to 5, 5 down to 1. 

1 -> 2 -> 5 -> 1 
3 -> 4 -> 3 

，我们将需要交换索引1与5，则索引5 2;以及索引3的索引3.共3次掉期或n - 2。我们减去n的周期数，因为循环元素一起总计n，每个循环表示一个交换次数小于其中元素的数量。

Answer 2

对于上述问题，下面是C的简单实现。该算法类似于用户גלעדברקן：

• 存放在b[]的a[]每个元素的位置。所以，b[a[i]] = i
• 从左到右迭代初始数组a[]。
• 在位置i，检查a[i]是否等于i。如果yes，然后继续迭代。
• 如果no，那么是时候交换了。仔细查看代码中的逻辑以了解交换如何进行。 这是最重要的一步，因为需要修改阵列a[]和b[]。增加掉期的count。

下面是执行：

long long sortWithSwap(int n, int *a) { 
    int *b = (int*)malloc(sizeof(int)*n); //create a temporary array keeping track of the position of every element 
    int i,tmp,t,valai,posi; 
    for(i=0;i<n;i++){ 
    b[a[i]] = i; 
    } 
    long long ans = 0; 
    for(i=0;i<n;i++){ 
    if(a[i]!=i){ 
     valai = a[i]; 
     posi = b[i]; 
     a[b[i]] = a[i]; 
     a[i] = i; 
     b[i] = i; 
     b[valai] = posi; 
     ans++; 
    } 
    } 
    return ans; 
} 

Answer 3

解决这个问题的本质在于以下观察
1.数组中的元素不重复
2.元素的范围是从0到n-1，其中n是数组的大小。

方法
当你理解了解决问题的方法之后，你可以在线性时间内解决问题。

想象一下在对所有条目进行排序后数组看起来像什么？
它看起来像arr [i] ==我，所有条目。这是否令人信​​服？

首先创建一个bool阵列名为FIX，其中FIX [I] == true，如果第i个位置是固定的，这个初始化数组假最初

开始检查匹配ARR原始数组[I] ==我，直到这个条件成立的时候，eveything没问题。在继续遍历数组的同时也更新FIX [i] = true。
当你发现arr [i]！= i
你需要做点什么，arr [i]必须有一些价值x使得x> i，我们如何保证？这个保证来自数组中的元素不重复的事实，因此如果数组被排序到索引i，那么它意味着数组中的位置i处的元素不能从左边来，而是从右边来。
现在x的值本质上是指一些索引，为什么这么说是因为数组只有从0开始到n-1为止的元素，并且在排序的arry中，数组中的每个元素i都必须位于i位置。
arr [i] == x意味着什么，不仅元素我不在它正确的位置，而且元素x从它的位置丢失。 现在要修复ith位置，您需要查看第x个位置，因为第x个位置可能会保留我，然后您将在索引i和x处交换元素，并完成工作。
但是等一下，没有必要索引x将持有我（你完成固定这些位置在1交换）。相反，索引x可能有可能存在值y，它又会大于i，因为数组只能排序到位置i。
现在，在您可以修复位置之前，您需要修复x，为什么？我们稍后会看到。
所以，现在再次尝试修复位置x，然后类似地，您将尝试修复，直到您未在时尚的某个位置看到元素i。
时尚是遵循arr [i]的链接，直到你在某个索引处击中元素i。
这是保证，你一定会打我在一些地点，而以这种方式。为什么？尝试证明它，做一些例子，你会感觉到
现在你将开始修复你在索引i之后的路径中看到的所有索引，直到这个索引（称为j）。现在你看到的是你所遵循的路径是循环路径，并且对于每个索引i，arr [i]都在前一个索引（索引从你到达的位置）开始，一旦你看到你可以修复索引，并将它们全部标记在FIX数组中为真。现在继续下一个数组索引，并做同样的事情，直到整个数组被修复..
这是完整的想法，但只有conunt no。交换，你认为一旦你找到了n个元素的周期，你需要n次交换，并且在这之后你修复了这个数组，并且再次继续。所以这就是你如何计算不。掉期。 请让我知道，如果你有一些疑问的方法。 您也可以要求提供C/C++代码帮助。
乐意帮忙:-)