[アーカイブ！】純粋数学、物理学、化学など：トレードとは一切関係ない脳トレ問題集 - ページ 584

[MikeM]

alsu:

1パスで。

同じサイズの配列の空のコピーを作成し，それをtwosで初期化する．

配列の先頭から移動します。出会い1-最初からコピーに書き込む、出会い3-最後からコピーに書き込む。

そして、twによる初期化（平均で66％の無駄）はパスではないのですか？
さらに、スリーポイントも同時にモニターしなければならないのです

[Dmitry Fedoseev]

GaryKa:

ちょっとしたタスクを与える。

もちろん、ハックですが、面接では配列ソートの知識の神格化として機能します ))

そこで、選別のためのタスク

N個のマスがあり、その中に1、2、3がランダムに配置されています。

最適なソートアルゴリズムを構築する。

1パスでカウントし、2パス目でアレイを 埋める。

[Alexey Subbotin]

alsu:

1パスで。

同じサイズの配列の空のコピーを作成し，それをtwosで初期化する．

配列の先頭から移動します。1に遭遇した場合は、先頭からのコピーに書き込み、3に遭遇した場合は、末尾からのコピーに書き込みます。

コピーなし（もしくは、コピー記入は別パスと言うことになります）。

n=0, m=0

アレイの先頭からスタートします。1に出会ったら、最初から1でないn番目の要素で変更し（構成上は常に2）、n++、3に出会ったら、最後からm番目の要素で変更し、3でないm++、1に出会ったら、最初の部分のステップに従います。

[Alexey Subbotin]

alsu:

コピーなし（または、コピー記入は別パスと言うことになる）

n=0, m=0

配列の先頭から行きます。1に出会ったら、最初からn番目の要素が1でないもの（構成上は必ず2になる）、n++に変え、3に出会ったら、最後からm番目の要素が3でないもの、m++に変え、1に出会ったら、前編で述べたように進めます。

平均で半パス、交換も同程度の時間

[sand]

alsu:

コピーなし（または、コピー記入は別パスと言うことになる）

n=0, m=0

配列の先頭から行きます。1に出会ったら、最初からn番目の要素が1でないもの（構成上は必ず2になる）、n++に変え、3に出会ったら、最後からm番目の要素が3でないもの、m++に変え、1に出会ったら、前編で述べたように進めます。

それは素晴らしいことです。

[TheXpert]

alsu:

パス回数を減らせば、必ず速度が上がるというわけではありません。

[MikeM]

配列の 2つの要素を交換するのは3つの操作です。高速化は望めない。

[Alexey Subbotin]

TheXpert:
パス回数を減らせば、必ず速度が上がるというわけではありません。

まあ、最適化基準は設定されていないのですが...。

[MikeM]

質問を投げかけさせてください。
A+B=...

[Dmitry Fedoseev]

alsu:

コピーなし（または、コピー記入は別パスと言うことになる）

n=0, m=0

配列の先頭から行きます。1に出会ったら、最初からn番目の要素が1でないもの（構成上は必ず2になる）、n++に変え、3に出会ったら、最後からm番目の要素が3でないもの、m++に変え、1に出会ったら、前編で述べたように進めます。

良いアイデアですね。