56. Merge Intervals的C++解法(重写sort函数)

题目描述：https://leetcode.com/problems/merge-intervals/

挑战中要求使用O(nlogn)的时间复杂度和O(1)的额外空间复杂度，所以使用了sort先对区间进行排序，然后在原容器上进行融合和删除操作，注意有删除操作之后i不需要自增了，后一个会自动移上来，如果无脑自增会跳过很多值。

但是这个方法比较慢。

class Solution {

public:

static bool cmp(const Interval &a,const Interval &b){

return (a.start

}

vector merge(vector &intervals) {

if (intervals.size()==0) return intervals;

sort(intervals.begin(),intervals.end(),cmp);

int head=intervals[0].start;

int tail=intervals[0].end;

int index=0;

int i=1;

while (i

{

if (intervals[i].start<=tail)

if (intervals[i].end<=tail) intervals.erase(intervals.begin()+i);

else

{

tail=intervals[i].end;

intervals[index].end=tail;

intervals.erase(intervals.begin()+i);

}

else

{

index=i;

head=intervals[i].start;

tail=intervals[i].end;

i++;

}

}

return intervals;

}

};

如果没有这个限制，可以考虑用类似hash表的方法做，本来我是用了vector，之后看到一个很棒的方法用了map，好处在于：

1.由于不知道数字的范围，不需要开很大的数组

2.vector处理不了[0,0]这样的情况,会判别为不存在，但是map即使是map[0]，也会被计算在内。

class Solution {

public:

vector merge(vector& intervals) {

map terminals;

for (auto& i : intervals){

terminals[i.start] += 1;

terminals[i.end] -= 1;

}

vector res;

int levels = 0,start;

for (auto& p : terminals){

//map是默认以key值排序的

int num = p.first,cnt = p.second;

if (levels == 0)//第一次碰上0是一个区间的开始

start = num;

levels += cnt;

if (levels == 0){//再一次碰上0是区间的结束

res.push_back(Interval(start,num));

}

}

return res;

}

};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!