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

 
alsu:

1パスで。

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

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


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

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

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


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

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

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


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

1パスで。

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

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

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

n=0, m=0

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

 
alsu:

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

n=0, m=0

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


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

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

n=0, m=0

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



それは素晴らしいことです。
 
alsu:
パス回数を減らせば、必ず速度が上がるというわけではありません。
 
配列の 2つの要素を交換するのは3つの操作です。高速化は望めない。
 
TheXpert:
パス回数を減らせば、必ず速度が上がるというわけではありません。
まあ、最適化基準は設定されていないのですが...。
 
質問を投げかけさせてください。
A+B=...
 
alsu:

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

n=0, m=0

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



良いアイデアですね。