ランダムに配列を塗りつぶす

Question

add（）を呼び出すことによって、配列がランダムな空の位置に塗りつぶされているデータ構造を構築しようとしています。ある位置が満たされると、別のadd（）によって上書きされることはありません。 remove（i）を呼び出すと、A [i]の位置が解放されます。 add（）とremove（）の呼び出しを混在させることができます。

私の最初の考えは、add（）が呼び出されるたびに0からn-1の間の数字をランダムに生成することでした。それが空であれば、それを記入してください。一杯になったら、空のものが見つかるまで順次検索してください。しかし、これには2つの問題があります。1）配列がほとんどいっぱいの場合、O（n）時間に近​​づきます。2）ランダム選択は一様ではありません。

2番目の考えは、1からn-1までのシャッフルを使用してこの順番で追加することでしたが、これはremove（）をサポートしていません。

これは、add（）とremove（）に対して一定のパフォーマンスを保証する方法を実装していますか？

Answer 1

空の配列位置と空の配列位置をリンクリストで区切っておくことができます。ここで、0から（考慮されているリンクリストの長さ、つまり塗りつぶしているか空であるか）をランダムに生成し、これを使用してリストからランダムな位置を選択します。 ここで、塗りつぶしリストから任意の要素を選択し、対応する項目を削除して空のリストに追加します。 リンクリストのトラバーサルにはO（リンクリストの長さ）の時間がかかりますが、add（）の実行中は塗りつぶし位置を選択し、remove（）を実行すると空の位置を選択する問題は解決します。

Answer 2

配列を塗りつぶして、work_array[]としましょう。 filled_positions[]とempty_positions[]の2つの補助配列を使用し、work_array[]のカウンターと、num_filledとnum_emptyという2つのカウンターを使用して、要素数をfilled_positions[]とempty_positions[]とします。アレイが0からインデックスされていると仮定すると、最初はnum_filledは0であり、empty_positions[]は0,1,2、...からn-1,num_emptyはnです。

• ランダムな位置に要素を追加する乱数R 0とnum_empty - 1間、包括生成

  1. 。
  2. インデックスを選択empty_positions[r]からです。
  3. がnum_empty-1未満の場合は、empty_positions[r]をempty_positions[num_empty-1]と設定します。
  4. デクリメントnum_empty。
  5. セットfilled_positions[num_filled]~i。
  6. 増分num_filled。
  7. work_array[i]に要素を入力します。ランダムな位置から要素を削除する

• ：

  1. 乱数R 0とnum_filled - 1間、包括的に生成します。
  2. インデックスを選択ifilled_positions[r]
  3. がnum_filled - 1未満の場合は、filled_positions[r]をfilled_positions[num_filled-1]と設定します。
  4. デクリメントnum_filled。
  5. セットempty_positions[num_empty]~i。
  6. 増分num_empty。

あなたはwork_array_map[i]が別途work_array[i]が満たされた場合に1と0であると、ビット、work_array_map[]の配列を維持することができます。 work_array_map[]を使用すると、一定時間内に要素iが満たされているかどうかを確認できます。