力扣打卡11：合并区间（比较器内联，引用传参的优化）

链接：56. 合并区间 - 力扣（LeetCode）

这道题可以用贪心。

首先将intervals的left（intervals[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 vector<int>& A, const vector<int>& B) {
    return A[0] < B[0];
}

当然，还可以使用引用传递，避免复制值，直接传递地址，防止造成的额外开销，（其实值的复制

才是最影响效率的）

bool cmp(vector<int>& A,vector<int>& B)
{
    return A[0]<B[0];
}

通过比较，可以看到，这方面的优化会提升不少i的程序运行效率。

下面是我的代码：

class Solution {
public:
    static bool cmp(vector<int> A,vector<int> B)
    {
        return A[0]<B[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //调用自己写的比较器，尤其是静态的，不会内联。每次调用比较函数都会有额外的函数调用开销。
        //sort(intervals.begin(),intervals.end(),cmp);     
        //默认的比较器默认比较intervals[i][0]
        //sort(intervals.begin(),intervals.end());
        //lambda表达式，会内联
        sort(intervals.begin(), intervals.end(), [](const vector<int>& A, const vector<int>& B) {
            return A[0] < B[0];
        });
        vector<vector<int>> ans;
        vector<int> t=intervals[0];
        for(int i=1;i<intervals.size();i++)
        {
            if(t[1]<intervals[i][0])
            {
                ans.push_back(t);
                t=intervals[i];
            }
            else
            {
                t[1]=max(t[1],intervals[i][1]);
            }
        }
        ans.push_back(t);
        return ans;
    }
};

原文地址：https://blog.csdn.net/Bigkinder/article/details/144357721

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！