我有一个未排序集合中的分层项目集合。每个项目都有一个字段 previousItem:
public class Item{
public Item previousItem;
}
处理这些项目的最有效方法是什么,以便输出是一个集合,其中没有任何 previousItem 的 Item 是集合中的第一个 Item,而每个后续项目的 previousItem 是集合中的前一个项目?
我的第一个想法是在 Item 类中实现 Comparable 接口(interface):
public int compareTo(Item that) {
final int BEFORE = -1;
final int EQUAL = 0;
final int AFTER = 1;
if(this.previousItem==null){
return BEFORE;
}
if(that.previousItem==null){
return AFTER;
}
if(this.previousItem.equals(that){
return AFTER;
}else if(that.previousItem.equals(this){
return BEFORE;
}
return EQUAL;
}
然后循环遍历这些项目并将它们添加到 TreeSet 中:
SortedSet<Item> itemSortedSet = new TreeSet<Item>();
for (Item item : itemCollection) {
itemSortedSet.add(item);
}
是否有更有效的方法(更少的处理时间/所需的迭代次数)来对集合进行排序,以便它们按逻辑、分层顺序排列?
最佳答案
您的比较器将不起作用:它不提供传递性,即如果您在 A->B->C 的情况下比较项目 A 和 C,它会做错误的事情。
如果没有项目可以具有相同的前一个项目,则您的Item
对象本质上形成一个基本的链接列表。如果您碰巧知道哪一项是最后一项,您可以从那里开始使用单个循环并解开整个结构:
Item last = ...;
while (last != null) {
result.add(last)
last = last.previousItem
}
如果您无法找出哪一项是最后一项,那么您可以使用 IdentityHashMap
将每个 previousItem
值映射到使用它的 Item
对象:
IdentityHashMap<Item,Item> m = new IdentityHashMap<Item,Item>(itemset.size());
for (Item i : itemset)
m.put(i.previousItem, i);
Item i = m.get(null);
while (i != null) {
result.add(i);
i = m.get(i);
}
这将从没有前一个节点的项目开始解开未排序的集合。
这两种方法都具有大致线性的复杂度。项目的数量,但他们做出了两个假设,这些假设在您的情况下可能无效:
每个项目只能是最多一个个其他节点的前一项,即您的项目是一个列表而不是树。
只有一个项目“线程”。
如果这些假设中的任何一个都不成立,您将需要一个更复杂的算法来解决这个问题。
关于Java:有一个项目集合,其中每个项目都有一个字段 "previousItem",对集合进行排序的最有效方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9664212/