私が見た問題は、荒波のようなものです。 http://judgecode.com/problems/1011Judgecode - スワップで並べ替え（
0からn-1までの整数の並べ替えを考えると、それらの並べ替えは簡単です。しかし、毎回一対の整数しか入れ替えることができない場合はどうすればよいでしょうか？
一つの古典的なアルゴリズムは、順列サイクルであるように思わスワップの最小数（https://en.wikipedia.org/wiki/Cycle_notation#Cycle_notation）を計算してください。必要なスワップの数は、エレメントの総数からサイクル数を差し引いたものに等しくなります。例えば
：我々は2でインデックス5、次いで、5とインデックス1を交換する必要がある
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
。インデックス3とインデックス4を使用します。合計3回のスワップまたはn - 2。 nをサイクル数で減算すると、サイクル要素は合計でnであり、各サイクルはその中の要素の数より少ないスワップを表します。
上記は、Cの単純な実装です。
b[]でa[]のすべての要素の位置：このアルゴリズムは、ユーザーגלעדברקןに似ています。したがって、b[a[i]] = ia[]を左から右に反復します。iの位置で、a[i]がiに等しいかどうかをチェックします。 yesの場合は、繰り返し実行してください。noの場合は、スワップする時間です。コード内のロジックを細かく見て、スワップの仕組みを確認してください。 これは配列a[]とb[]の両方を変更する必要があるため、最も重要なステップです。スワップのcountを増やしてください。ここで実装です。この問題を解決するための本質は、以下の観察
1である
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;
}
配列内の要素は
2に要素の範囲を繰り返さないでくださいされて0からn-1までです.nは配列のサイズです。
道に近づく
あなたが問題にアプローチする方法を理解した後は、それを線形時間で解くことができます。
想像してみてください。すべてのエントリを並べ替えた後の配列はどのように見えますか？
すべてのエントリに対して、arr [i] == iのように見えます。それは説得力がありますか？マッチARRのための元の配列をチェック
まず場所が固定であるITH FIX [i]を== trueの場合は、最初はfalseで、この配列を初期化する場合はFIXという名前のブール配列を作成
スタート[I] ==私は、この条件が成り立つ時まで、eveythingは大丈夫です。配列のトラバーサルを進めながら、FIX [i] = trueも更新します。
arr [i]！= i
あなたは何かする必要があります。arr [i]はx> iのような値xを持つ必要があります。この保証は、配列内の要素が繰り返されないという事実から保証されます。したがって、配列がインデックスiまでソートされていれば、配列内の位置iの要素は左からではなく右から来ることを意味します。
値xは本質的に何らかのインデックスについて言います。なぜなら、配列は0から始まるn-1までの要素しか持たず、並べ替えられたarryでは配列の各要素iは位置iになければなりません。
arr [i] == xとは、要素iが正しい位置にないだけでなく、要素xがその場所にないことを意味します。 i番目の位置を修正するにはx番目の位置を見る必要があります.x番目の位置がiを保持しているため、インデックスiとxの要素を入れ替えてジョブを完了させるためです。
ただし、インデックスxがiを保持する必要はありません（1回のスワップでこれらの場所を修正することができます）。むしろ、インデックスxは値yを保持する可能性があり、配列は位置iまでしかソートされないため、iは値yより大きくなります。
ポジションiを修正する前に、xを修正する必要があります。なぜですか？私たちは後で見るでしょう。
もう一度、位置xを固定しようとします。同様に、ファッションのある場所で要素iが見えなくなるまで固定します。
ファッションは、いくつかのインデックスで要素iをヒットするまで、arr [i]からのリンクに従うことです。
このようにしている間に、あなたは間違いなく私をいくつかの場所で打つことが保証されています。どうして ？それを証明しようとして、いくつかの例を作ってみてください。
次のパスで見たすべてのインデックスをインデックスiからこのインデックス（jと言う）まで固定し始めます。今あなたが見ているのは、あなたがたどった道は循環的なものであり、すべての索引iについて、それ以前の索引（あなたがここに到達したところの索引）にarr [i]が引かれています。索引を作成し、FIX配列のすべてをtrueにします。今度は配列の次のインデックスに進み、配列全体が固定されるまで同じことをします。
これは完全なアイデアでしたが、スワップが必要なn要素のサイクルが見つかると、n回のスワップが必要になります。その後、配列を修正してからやり直してください。そういうわけで、あなたはノー数を数えるでしょう。スワップの アプローチに疑問がある場合はお知らせください。 また、C/C++コードのヘルプを要求することもできます。
お手伝いください:-)