algorithm - 配列の要素を 3 つのグループに分割する

Question

配列の要素を 3 つのグループに分割する必要があります。これは、配列をソートせずに行う必要があります。例を考えてみましょう

120 個の並べ替えられていない値があるため、最小の 40 個の値を最初のグループに、次の 40 個を 2 番目のグループに、最大の 40 個を 3 番目のグループにする必要があります。

中央値アプローチの中央値を考えていましたが、それを私の問題に適用できませんでした。親切にアルゴリズムを提案してください。

Answer 1

注文統計を見てみましょう。統計サンプルの k 次統計は、その k 番目に小さい値に等しくなります。リストの k 番目に小さい (または最大の) 要素を計算する問題は、選択問題と呼ばれ、選択アルゴリズムによって解決されます。

中央値の中央値を考えるのは正しいです。ただし、中央値を見つける代わりに、配列から 20 番目と 40 番目に小さい要素の両方を見つけたい場合があります。中央値を見つけるのと同じように、選択アルゴリズムを使用して両方を見つけるのに線形時間しかかかりません。最後に、配列を調べて、これら 2 つの要素に従って要素を分割します。これも線形時間です。

PS。これがアルゴリズムクラスでの演習である場合、これは役立つかもしれません:)

Answer 2

入力配列と同じサイズの配列を割り当てて、入力配列を 1 回スキャンし、配列の最小値と最大値を追跡します。同時に、2 番目の配列のすべての値を 1 に設定します。計算しdelta = (max - min) / 3ます。配列を再度スキャンし、数値が の場合は 2 番目の配列を 2 に設定し > min+delta and < max-deltaます。それ以外の場合if >= max-deltaは 3 に設定します。その結果、番号がどのグループに属しているかを示す配列が得られます。すべての数値が互いに異なると仮定しています。複雑：O(2n)