1

我正在解决一个问题，我需要存储具有无重复和维护顺序要求的元素。我选择了，LinkedHashSet因为它满足了我的两个要求。

假设我有这个代码：

 LinkedHashSet hs = new LinkedHashSet();
  hs.add("B");
  hs.add("A");
  hs.add("D");
  hs.add("E");
  hs.add("C");
  hs.add("F");
  if(hs.contains("D")){
       //do something to remove elements added after"D" i-e remove "E", "C" and "F"
       //maybe hs.removeAll(Collection<?>c) ??
   }

谁能指导我删除这些元素的逻辑？

我使用了错误的数据结构吗？如果是这样，那么什么是更好的选择？

4

4 回答 4

3

如果您使用 LinkedHashSet，我认为您可能需要使用迭代器进行删除。也就是说找到元素，然后继续删除，直到找到尾部。这将是 O(n)，但是即使您编写了自己的 LinkedHashSet（带有双向链表和哈希集），您也可以访问原始链接结构，以便您可以在 O(1) 中剪切链表，但是您仍然需要从 HashSet 中删除刚刚从链表中删除的所有元素，这是 O(n) 成本再次出现的地方。

因此，总而言之，删除元素，然后为该元素保留一个迭代器，并继续向下删除元素，直到到达最后。我不确定 LinkedHashSet 是否公开了所需的调用，但您可能可以弄清楚。

于 2013-04-08T22:49:41.453 回答
0

这里的基本问题是您必须维护两个数据结构，一个表示键/值映射的“映射”，另一个表示插入顺序的“列表”。

有“地图”和“列表”组织可以在给定点之后快速删除元素；例如，各种有序树以及基于数组和链的列表（以定位点的成本为模。）

但是，似乎不可能从两个数据结构中删除 N 个元素O(N)。您必须访问所有要删除的元素才能将它们从第二个数据结构中删除。（事实上​​，我怀疑可以用数学方法证明这一点……）

简而言之，没有比您当前使用的数据结构更复杂的数据结构。

可以提高性能（使用自定义集合类！）的领域是避免显式使用迭代器。使用迭代器和标准迭代器 API，成本O(N)取决于数据结构中的元素总数。您可以根据O(N)删除的元素数量进行此操作……如果哈希条目节点也具有序列的下一个/上一个链接。

于 2013-04-08T23:09:47.667 回答
0

您可以编写自己的不允许重复的 ArrayList 版本，方法是覆盖add()和addAll()。据我所知，没有这样的“常见”第 3 方版本，这一直让我感到惊讶。有人知道吗？

然后删除代码非常简单（无需使用ListIterator）

int idx = this.indexOf("D");
if (idx >= 0) {
  for (int goInReverse = this.size()-1; goInReverse > idx; goInReverse--)
    this.remove(goInReverse);
}

但是，这仍然是 O(N)，因为您循环遍历列表的每个元素。

于 2013-04-08T23:40:25.840 回答
0

所以，在尝试了上面提到的几件事之后，我选择了实现不同的数据结构。因为我对这个问题的 O(n) 没有任何问题（因为我的数据非常小）

我使用了 Graphs，这个库非常方便：http: //jgrapht.org/

我正在做的是将所有元素作为顶点添加到DirectedGraph它们之间也创建边（边也帮助我解决了另一个不相关的问题）。当需要删除元素时，我使用带有以下伪代码的递归函数：

removeElements(element) {

tempEdge = graph.getOutgoingEdgeFrom(element)
if(tempEdge !=null)
   return;
tempVertex = graph.getTargetVertex(tempEdge)
removeElements(tempVertex)
graph.remove(tempVertex)

}

我同意图 DS 不适合这类问题，但在我的条件下，这非常有效……干杯！

于 2013-07-25T17:46:08.823 回答