我正在寻找具有以下属性的数据结构。
- 存储
tuple<Double,Integer,Integer>
的列表.订单仅在double
.具有相同 double 值的两个元组被认为是相同的。 - 支持重复。
- 需要能够按升序遍历。如果有重复,后面添加的顺序应该更高。
- 快速查找/插入
- 快速移除,注意移除总是遵循这个模式
方法包含移除:
for(int i=list.size()-1;i>=0;i--){// assume list is in ascending order
if(list[j:i] can be merged){
remove list[j:i-1];
update list[i]'s two integers;
i = j-1;
}
}
我目前使用 ArrayList 并对其进行排序。使用二进制搜索可以快速查找。然而,插入和删除将涉及内存中的大量副本,例如在列表前面插入会移动所有元素。
最佳答案
一个解决方案是对元组列表进行排序映射:
SortedMap<Double,List<Tuple<Integer,Integer>>>
声明行有点难看,但它会起作用。我以前曾多次使用 map 来列出 list 。它的好处是你可以从列表中删除项目,只要你的列表很短,你的移动次数就会减少。要遍历整个结构,您需要创建自己的迭代器,或调整您的原始代码。
关于java - 使用什么数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6860301/