0

我有一个需要按插入顺序遍历的列表。但是,我想通过在值上使用 floorEntry 和 ceilingEntry 来找到“起点”。

所以我需要一个具有以下所需操作的集合:

  1. 频繁插入/追加到结尾
  2. 需要像这样遍历:
    • 查找所有值 >= 或 <= (地板、天花板)
    • 然后按插入顺序遍历它
    • 删除符合条件的每个项目

所以集合需要按照插入的顺序进行排序,还需要根据排序后的值进行随机访问。

有没有类似 LinkedSortedMap 的东西?但不确定这也行得通。

如何在链表中找到值的第一个 floorEntry()?我怎样才能找到所有的 floorEntries 形成一个链表?

==============换句话说==============================

//I have timeseries of Ints.
TimeSeries<Int> collection = new LinkedList<>()

/*
FindAndRemove is to remove first n Ints that are <= x
*/

FindAndRemove1(Int x,int n) {
  //return an iter to filtered subset of collection
  iter = collection.floorEntrySet(x) 
  for (int i =0; i<n; i++) {  
    iter.remove()   
    if (!iter.hasnext) break; 
    iter->next
}


FindAndRemove2(Int x,int n) { 
   //return an collection.iter to oldest Int that is <= x
   iter = collection.floorEntry(x) 
   for ( int i = 0; iter.hasnext; iter.next ) {  
      if ( iter.x > x ) 
        continue;

      iter.remove()
      if ( ++i > n ) break;
   }
}
4

1 回答 1

0

如果您希望能够支持删除,那么您可以使用 TreeMap ,其中键是自动递增的整数

TreeMap<Integer, Object> sortedMap;
HashMap<Object, Integer> lookupMap;
int key;

public void add(Object obj) {
    sortedMap.put(key, obj);
    lookupMap.put(obj, key);
    key++;
}

使用查找映射在排序映射中查找对象的键,然后使用检索到的键对排序映射执行地板/天花板查询。

Google 有一个HashBiMap,您可以通过在一个方向使用哈希图和在另一个方向使用树图来适应您的需求

于 2013-06-10T18:35:42.383 回答