j*****p 发帖数: 41 | 1 给定一些不相交的区间和一个新的区间,要求合并起来
但问题是不让用新的vector/stack,也就是说要用constant additional space
请教大家
估计是挂了 |
p******4 发帖数: 31 | 2 merge interval?
【在 j*****p 的大作中提到】 : 给定一些不相交的区间和一个新的区间,要求合并起来 : 但问题是不让用新的vector/stack,也就是说要用constant additional space : 请教大家 : 估计是挂了
|
j*****p 发帖数: 41 | 3 对啊,这题不用新的vector或者是list怎么搞?
【在 p******4 的大作中提到】 : merge interval?
|
r*******k 发帖数: 1423 | 4 老的排个序
新的挨个和老的比较
能merge就把老的删掉,更新新的interval
碰到不能merge,算法就可以结束
【在 j*****p 的大作中提到】 : 给定一些不相交的区间和一个新的区间,要求合并起来 : 但问题是不让用新的vector/stack,也就是说要用constant additional space : 请教大家 : 估计是挂了
|
M*******a 发帖数: 1633 | 5 不用排序应该就可以,一个个和老的比。如果有哪个老的完全包含新的就结束,如果新
的完全包含老的老的删除,剩下的情况就是最多有两个老的分别和新的的上下边界相交
排序还要nlogn呢
【在 r*******k 的大作中提到】 : 老的排个序 : 新的挨个和老的比较 : 能merge就把老的删掉,更新新的interval : 碰到不能merge,算法就可以结束
|
r*******k 发帖数: 1423 | 6 我觉得根本不用考虑那么多
就遍历一下,能合并就删老的
一遍就行了
因为老的彼此都是不想交的
【在 M*******a 的大作中提到】 : 不用排序应该就可以,一个个和老的比。如果有哪个老的完全包含新的就结束,如果新 : 的完全包含老的老的删除,剩下的情况就是最多有两个老的分别和新的的上下边界相交 : 排序还要nlogn呢
|
M*******a 发帖数: 1633 | 7 我就这个意思
【在 r*******k 的大作中提到】 : 我觉得根本不用考虑那么多 : 就遍历一下,能合并就删老的 : 一遍就行了 : 因为老的彼此都是不想交的
|
t*******e 发帖数: 274 | 8 应该还有其他可能吧,比如新的区间落在两个老区间中间呢?还是说题目要求合并,所
以必然会有相交,而不用考虑这种情况
【在 M*******a 的大作中提到】 : 不用排序应该就可以,一个个和老的比。如果有哪个老的完全包含新的就结束,如果新 : 的完全包含老的老的删除,剩下的情况就是最多有两个老的分别和新的的上下边界相交 : 排序还要nlogn呢
|
M*******a 发帖数: 1633 | 9 那就什么都不用干啊,下一个阿
【在 t*******e 的大作中提到】 : 应该还有其他可能吧,比如新的区间落在两个老区间中间呢?还是说题目要求合并,所 : 以必然会有相交,而不用考虑这种情况
|
t*******e 发帖数: 274 | 10 重新想了一下,这和leetcode上的insert intervals 做法应该一样吧,虽然那个原始
区间都排过序了 |
|
|
j*****p 发帖数: 41 | 11 可是在c++中的vector或者是java中的List的iterator的时候,怎样能够删除又不引起
invalid iterator或者是concurrent modification exception呢?
能给个程序吗?我看到的解答都是创建新的vector或者是List
【在 r*******k 的大作中提到】 : 老的排个序 : 新的挨个和老的比较 : 能merge就把老的删掉,更新新的interval : 碰到不能merge,算法就可以结束
|
U***A 发帖数: 849 | 12 这个怎么样?
/*
merege interals
*/
void mergeIntervals(vector &vp, Pair np){
int size = (int)vp.size();
if(size == 0) {
vp.push_back(np);
return;
}
for(vector::iterator it = vp.begin(); it != vp.end();){
if(np.first > it->second || np.second < it->first){
it++;
}
else if(np.first > it->first && np.second < it->second){
return;
}
else if(np.first <= it->first && np.second >= it->second){
vp.erase(it);
}
else{
np.first = np.first < it->first ? np.first : it->first;
np.second = np.second > it->second? np.second : it->second;
vp.erase(it);
}
}
vp.push_back(np);
}
【在 j*****p 的大作中提到】 : 可是在c++中的vector或者是java中的List的iterator的时候,怎样能够删除又不引起 : invalid iterator或者是concurrent modification exception呢? : 能给个程序吗?我看到的解答都是创建新的vector或者是List
|
l*****a 发帖数: 14598 | 13 你可以连续调用
list.remove(cur)
相当于把list中cur,cur+1,cur+2..删除
然后list.insert(cur,**)
就是插在当前位置
【在 j*****p 的大作中提到】 : 可是在c++中的vector或者是java中的List的iterator的时候,怎样能够删除又不引起 : invalid iterator或者是concurrent modification exception呢? : 能给个程序吗?我看到的解答都是创建新的vector或者是List
|
j**********3 发帖数: 3211 | |
l*****a 发帖数: 14598 | 15 结果不需要顺序的话
你为什么要排序
【在 j**********3 的大作中提到】 : 排序然后binary search
|
j*****p 发帖数: 41 | 16 这里的vector.erase非常耗时吧?
我改了之后没有能够在leetcode上通过测试
【在 U***A 的大作中提到】 : 这个怎么样? : /* : merege interals : */ : void mergeIntervals(vector &vp, Pair np){ : int size = (int)vp.size(); : if(size == 0) { : vp.push_back(np); : return; : }
|
U***A 发帖数: 849 | 17 为什么耗时?
你怎么该的?
【在 j*****p 的大作中提到】 : 这里的vector.erase非常耗时吧? : 我改了之后没有能够在leetcode上通过测试
|
j*****p 发帖数: 41 | 18 vector insert(vector &intervals, Interval newInterval) {
int size = (int) intervals.size();
if (size == 0) {
intervals.push_back(newInterval);
return intervals;
}
for (vector::iterator it = intervals.begin(); it != intervals.
end();) {
if (newInterval.start > it->end || newInterval.end < it->start) {
it++;
} else if (newInterval.start > it->start && newInterval.end < it->
end) {
return intervals;
} else if (newInterval.start <= it->start && newInterval.end >= it->
end) {
it = intervals.erase(it);
} else {
newInterval.start = newInterval.start < it->start ? newInterval.
start : it->start;
newInterval.end = newInterval.end > it->end ? newInterval.end :
it->end;
it = intervals.erase(it);
}
}
intervals.push_back(newInterval);
return intervals;
}
【在 U***A 的大作中提到】 : 为什么耗时? : 你怎么该的?
|
j*****p 发帖数: 41 | 19 能否给个代码?我还自认为比较熟java,但发现硬是没有搞出来
【在 l*****a 的大作中提到】 : 你可以连续调用 : list.remove(cur) : 相当于把list中cur,cur+1,cur+2..删除 : 然后list.insert(cur,**) : 就是插在当前位置
|
r*******k 发帖数: 1423 | 20 不能先记下index,然后最后统一删除么?
啊,晕,这就相当于新建了List……
那从List的后面向前用index扫描呢?
碰到合并的就删除,这个没问题吧?
【在 j*****p 的大作中提到】 : 可是在c++中的vector或者是java中的List的iterator的时候,怎样能够删除又不引起 : invalid iterator或者是concurrent modification exception呢? : 能给个程序吗?我看到的解答都是创建新的vector或者是List
|
|
|
U***A 发帖数: 849 | 21 那是因为lc是排序的。所有最后应该找合适的位置插入newInterval.
这个可以
vector insert(vector &intervals, Interval
newInterval) {
int size = (int) intervals.size();
if (size == 0) {
intervals.push_back(newInterval);
return intervals;
}
for (vector::iterator it = intervals.begin(); it != intervals.
end();) {
if (newInterval.start > it->end || newInterval.end < it->start) {
it++;
} else if (newInterval.start > it->start && newInterval.end < it->
end) {
return intervals;
} else if (newInterval.start <= it->start && newInterval.end >= it->
end) {
it = intervals.erase(it);
} else {
newInterval.start = newInterval.start < it->start ? newInterval.
start : it->start;
newInterval.end = newInterval.end > it->end ? newInterval.end :
it->end;
it = intervals.erase(it);
}
}
for(int i=0; i
if(newInterval.end < intervals[i].start){
intervals.insert(intervals.begin()+i, newInterval);
return intervals;
}
}
intervals.push_back(newInterval);
return intervals;
}
{
intervals.
【在 j*****p 的大作中提到】 : vector insert(vector &intervals, Interval newInterval) { : int size = (int) intervals.size(); : if (size == 0) { : intervals.push_back(newInterval); : return intervals; : } : for (vector::iterator it = intervals.begin(); it != intervals. : end();) { : if (newInterval.start > it->end || newInterval.end < it->start) { : it++;
|
j*****p 发帖数: 41 | 22 怪了,之前我的提交说是用时太长了
【在 U***A 的大作中提到】 : 那是因为lc是排序的。所有最后应该找合适的位置插入newInterval. : 这个可以 : vector insert(vector &intervals, Interval : newInterval) { : int size = (int) intervals.size(); : if (size == 0) { : intervals.push_back(newInterval); : return intervals; : } :
|
j*****p 发帖数: 41 | 23 您要不写个例程给示范下?
【在 r*******k 的大作中提到】 : 不能先记下index,然后最后统一删除么? : 啊,晕,这就相当于新建了List…… : 那从List的后面向前用index扫描呢? : 碰到合并的就删除,这个没问题吧?
|
j**********3 发帖数: 3211 | 24 不排序咋binary search?
不用额外空间的话,就需要多次iteration?这样time complexity就增加了。。。
【在 l*****a 的大作中提到】 : 结果不需要顺序的话 : 你为什么要排序
|
l*****7 发帖数: 55 | 25 vector 的 erase()复杂度是O(n)啊,岂不费时?最坏就O(n^2)了。设想新的区间包含
所有已知区间。
在erase那里可以考虑把最后一个区间swap过来;或者在线partition,最后删除重合的
区间就行了。
【在 U***A 的大作中提到】 : 为什么耗时? : 你怎么该的?
|
j*****p 发帖数: 41 | 26 对,之前我就是因为这个而超时了
【在 l*****7 的大作中提到】 : vector 的 erase()复杂度是O(n)啊,岂不费时?最坏就O(n^2)了。设想新的区间包含 : 所有已知区间。 : 在erase那里可以考虑把最后一个区间swap过来;或者在线partition,最后删除重合的 : 区间就行了。
|
t*******e 发帖数: 274 | 27 上面用iterator的方法是不错,不过这还算是O(1) space么 |
s*****n 发帖数: 350 | 28 一遍肯定不行啊
【在 r*******k 的大作中提到】 : 我觉得根本不用考虑那么多 : 就遍历一下,能合并就删老的 : 一遍就行了 : 因为老的彼此都是不想交的
|
l**********1 发帖数: 415 | 29 还是要排序吧,因为老的和新的合并后的新区间可能和其它老区间重合。除非题目没要
求合并所有重合区间。 |
r*******e 发帖数: 971 | |
|
|
x******9 发帖数: 473 | 31 +1
【在 t*******e 的大作中提到】 : 重新想了一下,这和leetcode上的insert intervals 做法应该一样吧,虽然那个原始 : 区间都排过序了
|
a*****y 发帖数: 22 | 32 看了大家的回复,得到启发,思路如下:
遍历两遍:第一遍确定如下情况:
1, 新区间可以被原有的某个区间包含,直接返回
2, 新区间与原有的区间都不相交,push_back,返回
3, 相交,又分为两种情况:(1)新区间完全覆盖原有某区间,将改区间置为无效(
opening > close) (2)部分相交:更新新区间的头或尾,将原有的那个区间置为无效
第二遍遍历,删掉标记为无效的区间
总时间复杂度为O(n)
struct Interval {
int opening;
int close;
};
void MergeInterval(std::vector& org, Interval new_interval) {
int n = org.size();
if (n == 0) {
return;
}
bool is_intersected = false;
for (int i = 0; i < n; ++i) {
if (org[i].opening <= new_interval.opening) {
if (org[i].close >= new_interval.close) {
return;
} else if (org[i].close < new_interval.opening) {
continue;
}
is_intersected = true;
new_interval.opening = org[i].opening;
org[i].close = org[i].opening - 1;
} else {
if (new_interval.close < org[i].opening) {
continue;
} else if (new_interval.close < org[i].close) {
new_interval.close = org[i].close;
}
is_intersected = true;
org[i].close = org[i].opening - 1;
}
}
org.push_back(new_interval);
if (!is_intersected) {
return;
}
int deleted_num = 0;
for (int i = 0; i + deleted_num < n; ) {
if (org[i + deleted_num].opening > org[i + deleted_num].close) {
++deleted_num;
continue;
}
if (deleted_num > 0) {
org[i].opening = org[i + deleted_num].opening;
org[i].close = org[i + deleted_num].close;
}
++i;
}
org.resize(n - deleted_num);
} |
M*****M 发帖数: 20 | 33 同意!
如果像leetcode insert interval里区间vector已经排序,不用创建新vector, 只需
一步erase 和 insert, O(n)
vector insert(vector &intervals, Interval
newInterval) {
auto start = intervals.begin();
auto it= start;
for(; it !=intervals.end(); ++it) {
if(newInterval.endstart) {
//insert newinterval here
//before insertion, erase prev intervals which are already
merged to newinterval
it = intervals.erase(start, it);
intervals.insert(it, newInterval);
return intervals;
} else if (newInterval.start>it->end){
//newinterval has bigger start
start++;
} else {
//cur interval and newinterval have overlap
newInterval.start = min(it->start, newInterval.start);
newInterval.end = max(it->end, newInterval.end);
}
}
if(start!=it) {
//this is the case that newinterval includes all intervals
it = intervals.erase(start, it);
}
intervals.insert(it, newInterval);
return intervals;
}
如果区间vector没排序,就一个一个删
vector insert(vector &intervals, Interval
newInterval) {
auto it= intervals.begin();
for(; it !=intervals.end(); ) {
if(newInterval.endstart||newInterval.start>it->end) {
it++;
} else {
//cur interval and newinterval have overlap
newInterval.start = min(it->start, newInterval.start);
newInterval.end = max(it->end, newInterval.end);
it = intervals.erase(it);
}
}
intervals.insert(it, newInterval);
return intervals;
}
【在 r*******k 的大作中提到】 : 我觉得根本不用考虑那么多 : 就遍历一下,能合并就删老的 : 一遍就行了 : 因为老的彼此都是不想交的
|
g*****y 发帖数: 94 | 34 Java 版的in-place,只能说实现起来太恶心啦。
public List insert(List intervals, Interval newInterval)
{
if (intervals == null) {
return intervals;
} else if (intervals.size() == 0) {
intervals.add(newInterval);
return intervals;
}
int size = intervals.size();
int left = findLastLess(intervals, newInterval);
int right = findFirstLarger(intervals, newInterval);
if (left < 0 || newInterval.start > intervals.get(left).end) {
++left;
}
if (right >= size || newInterval.end < intervals.get(right).start) {
--right;
}
for (int i = left; i <= right; ++i) {
newInterval.start = Math.min(newInterval.start, intervals.get(
left).start);
newInterval.end = Math.max(newInterval.end, intervals.get(left).
end);
intervals.remove(left);
}
intervals.add(left, newInterval);
return intervals;
}
private static int findLastLess(List intervals,
Interval newInterval) {
int low = 0, high = intervals.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (newInterval.start < intervals.get(mid).start) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return high;
}
private static int findFirstLarger(List intervals,
Interval newInterval) {
int low = 0, high = intervals.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (newInterval.end <= intervals.get(mid).end) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
} |