网站开发公司 网站空间,足球比赛直播现场在线观看,移动互联网终端,网站代理公司链接#xff1a;56. 合并区间 - 力扣#xff08;LeetCode#xff09; 这道题可以用贪心。
首先将intervals的left#xff08;intervals[i][0]#xff09;排序。
然后拿出第一个区间#xff0c;比较后面相邻的区间#xff1a;
当前right后left#xff0c;表示下一…链接56. 合并区间 - 力扣LeetCode 这道题可以用贪心。
首先将intervals的leftintervals[i][0]排序。
然后拿出第一个区间比较后面相邻的区间
当前right后left表示下一个区间独立了没有与前一个区间重叠的了。
当前right后left表示重叠了因为left排序了因此right选择大的就行。
其中在这道题里我还学到了对于排序时的比较器函数它有一些说法。
我首先用了自己写的静态比较器因为sort不是类内函数cmp如果不是静态就会报错将cmp写在类外也行但是这样的话排序的每次比较都会调用函数造成开销同时是值传递会复制值造成开销。因此程序运行时的速度会很慢。 但是我们可以使用内联增加编译的时间减少运行的时间。可以通过以下方法内联
1.lambda表达式
2.sort默认比较器默认的比较器默认比较intervals[i][0]
3.inline标记函数注意要const。因为sort传递给比较函数的参数通常是const对象因此函数签名与默认行为不匹配可能导致编译器拒绝内联甚至报错。
inline bool cmp(const vectorint A, const vectorint B) {return A[0] B[0];
}
当然还可以使用引用传递避免复制值直接传递地址防止造成的额外开销其实值的复制
才是最影响效率的
bool cmp(vectorint A,vectorint B)
{return A[0]B[0];
} 通过比较可以看到这方面的优化会提升不少i的程序运行效率。
下面是我的代码
class Solution {
public:static bool cmp(vectorint A,vectorint B){return A[0]B[0];}vectorvectorint merge(vectorvectorint intervals) {//调用自己写的比较器尤其是静态的不会内联。每次调用比较函数都会有额外的函数调用开销。//sort(intervals.begin(),intervals.end(),cmp); //默认的比较器默认比较intervals[i][0]//sort(intervals.begin(),intervals.end());//lambda表达式会内联sort(intervals.begin(), intervals.end(), [](const vectorint A, const vectorint B) {return A[0] B[0];});vectorvectorint ans;vectorint tintervals[0];for(int i1;iintervals.size();i){if(t[1]intervals[i][0]){ans.push_back(t);tintervals[i];}else{t[1]max(t[1],intervals[i][1]);}}ans.push_back(t);return ans;}
};
