20

この質問はプログラミングのインタビュー本であることがわかりました。ここでは質問を単純化しています。

Alengthの配列があり、同様に lengthnの順列配列があるとします。メソッドは、 の要素が で指定されたインデックスの順序で表示される配列を返します。PnAP

簡単な例: あなたのメソッドはA = [a, b, c, d, e]とを取りますP = [4, 3, 2, 0, 1]。その後、それは戻り[e, d, c, a, b]ます。一定のスペースのみを使用できます (つまり、O(n)スペースを取る別の配列を割り当てることはできません)。

アイデア？

4

9 に答える 9

7

さらに別の不必要な答え！これは順列配列Pを明示的に保存します。これは私の状況では必要でしたが、コストが犠牲になります。また、これは正しく配置された要素を追跡する必要はありません。以前の回答が解決策を提供していることを理解しているO(N)ので、これは娯楽のためだけだと思います!

最良のケースの複雑さO(N)、最悪のケースO(N^2)、および平均的なケースを取得しますO(NlogN)。大規模な配列 (N~10000またはそれ以上) の場合、平均的なケースは基本的にO(N)です。

Java のコア アルゴリズムは次のとおりです (つまり、疑似コード *せきせき*)

int ind=0;
float temp=0;

for(int i=0; i<(n-1); i++){
  // get next index
  ind = P[i];
  while(ind<i)
    ind = P[ind];

  // swap elements in array
  temp = A[i];
  A[i] = A[ind];
  A[ind] = temp;
}

実行中のアルゴリズムの例を次に示します (以前の回答と同様)。

A = [a、b、c、d、e]とする

および P = [2, 4, 3, 0, 1]

次に期待される = [c、e、d、a、b]

i=0:  [a, b, c, d, e] // (ind=P[0]=2)>=0 no while loop, swap A[0]<->A[2]
       ^     ^
i=1:  [c, b, a, d, e] // (ind=P[1]=4)>=1 no while loop, swap A[1]<->A[4]
          ^        ^
i=2:  [c, e, a, d, b] // (ind=P[2]=3)>=2 no while loop, swap A[2]<->A[3]
             ^  ^
i=3a: [c, e, d, a, b] // (ind=P[3]=0)<3 uh-oh! enter while loop...
                ^
i=3b: [c, e, d, a, b] // loop iteration: ind<-P[0]. now have (ind=2)<3
       ?        ^
i=3c: [c, e, d, a, b] // loop iteration: ind<-P[2]. now have (ind=3)>=3
             ?  ^
i=3d: [c, e, d, a, b] // good index found. Swap A[3]<->A[3]
                ^
done.

このアルゴリズムは、反復中の最大回数までwhile、任意の index に対してそのループ内を跳ね回ることができます。最悪の場合 (私が思うに!)、外側のループを反復するたびにループから追加の代入が発生するため、算術級数が発生し、複雑さが増します! ただし、これを の範囲で実行し、ループに必要な「余分な」割り当ての数を平均すると(つまり、それぞれの多くの順列の平均)、平均的なケースが であることが強く示唆されます。j<iiithforiwhileN^2NwhileNO(NlogN)

ありがとう！

于 2017-01-04T20:37:05.513 に答える
0

その結果、次の反復ステップでサイズ (n-1) の残りの配列を操作しながら、目的の要素を配列の前に置くことができます。

順列配列は、配列のサイズの減少を反映するように調整する必要があります。つまり、前に配置した要素が位置「X」で見つかった場合、順列テーブル内の X 以上のすべてのインデックスを 1 減らす必要があります。

あなたの例の場合：

array                   permutation -> adjusted permutation

A  =  {[a  b  c  d  e]}                 [4 3 2 0 1]
A1 =  { e [a  b  c  d]}   [3 2 0 1] ->    [3 2 0 1] (decrease all indexes >= 4)
A2 =  { e  d [a  b  c]}     [2 0 1] ->      [2 0 1] (decrease all indexes >= 3)
A3 =  { e  d  c [a  b]}       [0 1] ->        [0 1] (decrease all indexes >= 2)
A4 =  { e  d  c  a [b]}         [1] ->          [0] (decrease all indexes >= 0)

もう一つの例：

A0 = {[a  b  c  d  e]}                  [0 2 4 3 1]
A1 = { a [b  c  d  e]}     [2 4 3 1] ->   [1 3 2 0] (decrease all indexes >= 0)
A2 = { a  c [b  d  e]}       [3 2 0] ->     [2 1 0] (decrease all indexes >= 2)
A3 = { a  c  e [b  d]}         [1 0] ->       [1 0] (decrease all indexes >= 2)
A4 = { a  c  e  d [b]}           [0] ->         [0] (decrease all indexes >= 1)

このアルゴリズムは、最速ではありませんが、要素の初期順序を追跡しながら、余分なメモリ割り当てを回避します。

于 2013-05-11T21:31:38.740 に答える
0

ここでは、インデックスを受け入れる swapElements 関数を使用するより明確なバージョンがあります。たとえば、std::swap(Item[cycle], Item[P[cycle]])$ 本質的にすべての要素を実行し、まだアクセスされていない場合はサイクルに従います。2 番目の check の代わりに、!visited[P[cycle]]上記のどこかで行われたサイクルの最初の要素と比較することもできます。

 bool visited[n] = {0};
 for (int i = 0; i < n; i++)   {
     int cycle = i;
     while(! visited[cycle] && ! visited[P[cycle]]) {
         swapElements(cycle,P[cycle]);
         visited[cycle]=true;
         cycle = P[cycle];
     }
 }
于 2018-11-06T18:40:39.763 に答える