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++代碼幫助。
樂意幫忙:-)