C# · 12月 20, 2021

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<b.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<intervals.size())

{

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;

}

};