s*******h
发帖数: 3219 | 1 很奇怪，用二分法插入新interval 的start值，再用二分法查看要不要merge 该
interval 的end 值to existing intervals 。
在网上没看到有人这么做。难道我想错了？ |
s*******h
发帖数: 3219 | |
t**********g
发帖数: 3388 | |
H****r
发帖数: 2801 | 4 怎么没有，这题我面过，就是用的二分查找先
★ 发自iPhone App: ChineseWeb 7.8
【在 s*******h 的大作中提到】
: 很奇怪，用二分法插入新interval 的start值，再用二分法查看要不要merge 该
: interval 的end 值to existing intervals 。
: 在网上没看到有人这么做。难道我想错了？
|
z****e
发帖数: 54598 | 5 我用这种方法做了一遍
吭哧吭哧码出代码来
后来发现，java的list的add(int, object)方法
比add(object)方法开销要大要耗时
最后超时，还不如一开始就声明一个list
然后挨个往上add，又简单效率又高 |
p*****2
发帖数: 21240 | |
l**********r
发帖数: 4612 | 7 线性insert On, 二分查找插入Ologn
【在 p*****2 的大作中提到】
: 时间复杂度有改善吗？
|
s*******h
发帖数: 3219 | |
r*********n
发帖数: 4553 | 9 O(logN) search implemented using STL set
void insert_interval(set>& intervals, const pair&
newint){
set last;
for(auto& r : intervals){
last.insert(r.second);
}
auto beg = last.lower_bound(newint.first);
auto end = intervals.lower_bound(make_pair(newint.second, 0));
if( (*end).first == newint.second ) ++end;
if( beg == end ){
intervals.insert(newint);
}else{
auto it = intervals.begin() + beg - last.begin();
auto tmp = make_pair( min((*it).first, newint.first),
max((*(end-1)).second, newint.second) );
intervals.erase(it, end);
intervals.insert(tmp);
}
} |
l*n
发帖数: 529 | 10 挖个坟。
你这个结论是错的，二分查找要求必须是ArrayList，但是如果是ArrayList的话，
merge区域before/after区段的拷贝还是要O(n)(新建ArrayList作为返回值)；而如果完
全使用原ArrayList，因为ArrayList没有public的区段删除方法，每次remove(i)的时
候都是O(n)。只有LinkedList处理after区段是O(1)，但是before区段还是O(n)，而且
二分就不存在了。综上，还是线性处理+新建ArrayList吧。
【在 l**********r 的大作中提到】
: 线性insert On, 二分查找插入Ologn
|
