2 回答
TA贡献1982条经验 获得超2个赞
正如Alencar建议的那样,使用Collections.binarySearch(yourList, key, comparator)找到正确的插入位置。这比查找整个列表要快得多,因为binarySearch只需要 log2(列表大小)查询即可找到正确的插入位置。
所以,如果你的插入代码是
void sortedInsert(List<T> list, T value, Comparator<T> comparator) {
int pos=0;
ListIterator<T> it=list.listIterator();
while (it.hasNext() && comparator.compare(value, it.next()) < 0) pos ++;
if (pos < it.previousIndex()) it.previous();
it.add(value);
}
...更快的版本将是...
void sortedInsert2(List<T> list, T value, Comparator<T> comparator) {
int pos = Collections.binarySearch(list, value, comparator);
if (pos < 0) {
pos = -pos -1; // returns negatives if not found; see javadoc
}
list.insert(value, pos);
}
请注意,差异可能不是那么大,因为插入非链表需要向上移动元素。因此,如果基础列表是ArrayList,则平均而言,将一半的元素复制到右侧一个位置以为新元素腾出位置会导致O(n)每次复制额外的时间。如果列表是链接的,你仍然需要付出代价O(n),但这次是执行二分搜索——在这种情况下,使用第一个版本可能会更好。
请注意,第一个版本使用 aListIterator以防您决定使用链表。对于,使用和ArrayLists会更容易,但在迭代链表的上下文中,这是一个非常糟糕的主意。list.get(pos)list.add(pos, value)
TA贡献1744条经验 获得超4个赞
你不能在“正确”的地方添加对象吗?已经排序了吗?
您说过每次添加新对象时都会对列表/集合进行排序。
也许您可以使用二进制搜索来查找插入新值所需的确切索引或使用比较器来查找。
添加回答
举报