3

a と b の 2 つの配列があるとします。a のデータは完全に隠されています。で実行できる唯一の操作は、2 つの要素を交換することです。b のデータは完全に公開され、変更可能です。

位置 i の b の値は、a[i] に格納されている値の宛先を示します。つまり、b[3] = 7 の場合、a[3] の値を a[7] に移動します。a のスワップ操作のみを使用して、配列 b の情報に従って配列 a を変更するアルゴリズムを作成しようとしています (線形時間と定数空間が望ましい)。例として：

if   a  = { a b c d e f }
and  b  = { 1 3 2 0 5 4 }
then a' = { d a c b f e }
(ie, a[i] = a'[b[i]])

私は b を反復処理し、陽気に a.Swap(i, b[i]) を実行するという単純なアプローチを試みましたが、その間ずっと口笛を吹いていましたが、それは自分自身を上書きし、すでに適切な場所にあるデータを移動することになりました (あなたは推測するかもしれません）。

編集：これは実際には線形時間でなければなりません。これは並列ソート アルゴリズム用であるため、速度が最も重要です。

4

2 に答える 2

1

Goでの解決策:

for i := 0; i != len(b); i++ {
    for b[i] != i {
        a.Swap(i, b[i])
        b.Swap(i, b[i])
    }
}

これはすぐに O(n) に見えないかもしれませんが、

  • すべての a.Swap() は、a の少なくとも 1 つの要素を最終位置に配置します
    • 要素が最終的な位置にあると、再び交換されることはありません
    • したがって、最大でn回のスワップがあります
  • テストはスワップごとに 1 回、b[i] != ii ごとに 1 回余分に実行されます。
    • したがって、最大で 2n 個のテストがあります

ご覧のとおり、このアルゴリズムは時間では O(n)、空間では O(1) です。

于 2012-08-13T10:14:02.407 に答える
0

b の要素を昇順に並べ、b の要素を入れ替えながら、a の要素も入れ替えます。たとえば、バブル ソートを使用すると、次のようになります。

for(int i=0;i<b.length;i++){
for(int j=0;j<b.length-i-1;j++){
if(b[j+1]<b[j]){
// swap b[j+1] and b[j]
// swap a[j] and a[j+1]
}
}
}
于 2012-08-13T07:17:49.733 に答える