我正在寻找一种数据结构(或多种数据结构),它可以让我维护一个整数有序列表,没有重复值,且索引和值在相同的范围内。
我需要四个主要操作具有高效性,大概按照重要性顺序排序:
- 从给定索引获取值
- 查找给定值的索引
- 在给定索引处插入值
- 删除给定索引处的值
使用数组,1的时间复杂度是O(1),但2是O(N),而且插入和删除都很昂贵(我认为也是 O(N))。
链表的插入和删除时间复杂度是O(1)(一旦你有了节点),但1和2是O(N),因此抵消了收益。
我尝试保持两个数组a[index]=value和b[value]=index,这样就能使得1和2的时间复杂度变成O(1),但3和4的操作变得更加代价高昂。
是否有更适合此需求的数据结构?