3

次の配列があるとします。

1, 4, 5, 2, 3

私はそれを再配置する必要があります

5, 1, 4, 2, 3

余分なスペースだけがあります。1つint。

私はそれを解決するための1つの解決策を考え出しました。しかし、それはO(n^2)複雑さです。

誰かがより速い解決策を提供できますか？

ありがとう

編集済み：申し訳ありませんが、アレイを回転させていません。

元の配列を結果の配列に変更する必要があります。順序は任意です。私はただA->Bを作る必要があります。Bは私に言われます。

ありがとう

編集済み2"

明確にします。配列Bは固定されていません。これに対する一般的な解決策を見つける必要があります。

更新しました：

皆さん、ありがとうございました。これは頭​​の体操の質問のようです。ハハ：D

私の友人はこれについてAmazonのインタビュアーから頼まれました。笑

4

4 に答える 4

2

これは、配列をソートする特殊なケースであり、ソート順はかなり任意であるように思われます。したがって、最適なアルゴリズムの時間計算量はO（n log n）であり、インプレースソートを実行するアルゴリズムを使用すると（安定ソートではないという犠牲を払って）、スペースの複雑さはO（1）になります。平均O（n log n）がOKの場合のインプレースクイックソートと同様に、インプレースマージソートは法案に適合します。

于 2012-04-03T23:21:54.287 に答える
1

このソリューションは、O（1）スペースを使用して機能します。

>>> def arrayswap(source, dest):
...     for i in range(len(dest)):
...         source[source.index(dest[i])], source[i] = source[i], source[source.index(dest[i])]
... 
>>> a = [1, 4, 5, 2, 3]
>>> b = [5, 1, 4, 2, 3]
>>> arrayswap(a, b)
>>> a
[5, 1, 4, 2, 3]

Pythonのタプルパッキングを使用せずに、source[i]またはsource[source.index（dest [i]）]のいずれかの値をintに格納できます。

于 2012-04-03T23:48:51.180 に答える
0

最初の3つの要素を左に移動しているようです（ラップアラウンドあり）。

したがって、インデックス3と4は無視してください。

  int temp = array[0]
  array[0] = array[1]
  array[1] = array[2]
  array[2] = temp
于 2012-04-03T23:21:54.023 に答える
-1

あなたはただすることができます：

temp = arr[0];
arr[0] = arr[2];
arr[2] = arr[4];
arr[4] = arr[1];
arr[1] = arr[3];
arr[3] = temp;

編集：

配列aを配列bとして再配置するには、次のようにします。

for (var i = 0; i < a.length; i++) {
  for (var j = i + 1; a[i] != b [i]; j++) {
    var temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

}

デモ： http： //jsfiddle.net/Guffa/5sKdM/

これにbig-Oが何であるかはわかりませんが、サンプルデータでは、7回の比較と2回のスワップが行われるため、O（n 2）よりも間違いなく優れています。

また、何が「余分なスペース」としてカウントされるのか正確にはわからないので、これが1つの余分なスペースの要件を満たしているかどうかはわかりませんが、満たさない場合は、現在受け入れられている答えもありません...

于 2012-04-03T23:07:21.160 に答える