arrays - 配列の最大占有インデックスの追跡

Question

私は頻繁に（そして事実上ランダムに）要素を追加および削除している配列を持っています。配列の最大占有インデックスを追跡するアルゴリズムはありますか?

今、私が考えることができる最高のものは次のとおりです。

1. 変数 (つまり、HOI) で占有されている最大のインデックスを追跡します。
2. 配列内の次の空きインデックスを取得するときに、それが HOI よりも大きいかどうかを確認し、そのインデックスが HOI に割り当てられている場合
3. そのアイテムが HOI インデックスにある場合にそのアイテムを削除するときは、使用されているインデックスが見つかるまで HOI から逆方向にスキャンし、それを HOI に割り当てます。

これは機能するはずですが、特にエレガントではないので、誰かがよりクリーンなソリューションを知っているかどうか疑問に思っていました

Answer 1

アレイの密度に大きく依存します。

少なくとも適度に密度の高い配列の場合、次のアイテムが遠すぎないため、ソリューションは問題ありません。

非常にまばらな配列の場合、インデックスの二次データ構造は良い考えかもしれません (例: max heap )。

配列で立ち往生していますか？データ構造の選択を常に検討する必要があります。ここからは、解決しようとしている問題について十分な知識がないため、何が最善かを判断するのは困難です。

または、ソリューションのもう少し複雑なバージョンを検討することもできます。

• 最高のインデックスの最大 5 (またはその程度) のセット (小さい場合は並べ替えられた配列で問題ありません) を用意します。
• 挿入時に、最小の要素よりも大きい場合にのみ、このセットに追加します (要素が 5 つを超える場合は、最小の要素を削除します)。
• 削除時に、存在する場合はセットから削除します。セットが空の場合、削除されたインデックスを保存します。
• 最高になると、セット内の最大値を返すだけです。セットが空の場合、格納されたインデックスから逆方向に移動して最大値を見つけます (そしてそれをセットに追加します)。