arrays - 跟踪数组的最高占用索引

Question

我有一个数组，我经常（并且有效地随机）添加和删除元素。是否有跟踪数组的最高占用索引的算法？

目前我能想到的最好的方法如下：

1. 跟踪变量中占用的最高索引（即 HOI）。
2. 获取数组中的下一个空闲索引时，检查它是否高于 HOI，是否将该索引分配给 HOI
3. 删除项目时，如果该项目位于 HOI 索引处，则从 HOI 向后扫描，直到找到占用的索引并将其分配给 HOI

这应该可以，但它不是特别优雅，所以我想知道是否有人知道更清洁的解决方案

Answer 1

它很大程度上取决于阵列的密度。

对于至少适度密集的数组，您的解决方案很好，因为下一项不会太远。

对于非常稀疏的数组，索引的辅助数据结构可能是一个好主意（例如，最大堆）。

你被数组困住了吗？您应该始终考虑检查您选择的数据结构。从这里开始，很难说出什么是最好的，因为我对您要解决的问题了解得不够多。

或者您可以考虑稍微复杂一点的解决方案：

• 拥有一组最多 5 个（左右）最高索引的集合（排序数组如果很小的话也可以）。
• 在插入时，仅当它大于最小元素时才添加到此集合中（如果最小元素超过 5 个元素，则删除它）。
• 移除时，如果存在，则从集合中移除。如果集合为空，则存储删除的索引。
• 在获取最高值时，只需返回集合中的最大值。如果集合为空，则从存储的索引向后查找最大值（并将其添加到集合中）。