石家庄免费网站建设,网上商城网址怎么写,那些使用vue做的网站,搜索引擎优化的流程文章目录 Tag题目来源解题思路方法一#xff1a;平衡二叉搜索树 写在最后 Tag
【平衡二叉搜索树】【设计类】【2023-12-16】 题目来源
2276. 统计区间中的整数数目 解题思路
方法一#xff1a;平衡二叉搜索树
思路
用一棵平衡二叉搜索树维护插入的区间#xff0c;树中的… 文章目录 Tag题目来源解题思路方法一平衡二叉搜索树 写在最后 Tag
【平衡二叉搜索树】【设计类】【2023-12-16】 题目来源
2276. 统计区间中的整数数目 解题思路
方法一平衡二叉搜索树
思路
用一棵平衡二叉搜索树维护插入的区间树中的区间两两不想交。
当插入一个新区间时需要找到所有与该区间有重合整数的区间将这些区间合并后并将合并后的区间插入到平衡树中。
区间包含左端点 l 和右端点 r 两个属性在树中参与排序的是左端点。提前说明一下后文提到的大区间指的是左端点大。
当插入一个新的区间 [left, right]需要先找到树中和该区间可能有重复整数的最大区间 interval即树中满足 interval.l right 的区间如果区间 [left, right] 和区间 interval 相交则将它们合并。然后继续寻找这样的区间直到不存咋这样的区间或者找到的区间和待插入的区间不想交。同时用一个整数 cnt 维护树中区间覆盖的整数个数当调用 count 时直接返回 cnt。
算法
class CountIntervals {
private:mapint, int mp;int cnt 0;
public:CountIntervals() {}void add(int left, int right) {auto interval mp.upper_bound(right); // 找出 mp 中 right 的第一个 leftif (interval ! mp.begin()) {interval --;}while (interval ! mp.end() interval-first right interval-second left) {int l interval-first, r interval-second;left min(left, l);right max(right, r);cnt - r - l 1;mp.erase(interval);interval mp.upper_bound(right);if (interval ! mp.begin()) {interval --;}}cnt right - left 1;mp[left] right;}int count() {return cnt;}
};/*** Your CountIntervals object will be instantiated and called as such:* CountIntervals* obj new CountIntervals();* obj-add(left,right);* int param_2 obj-count();*/复杂度分析
时间复杂度add 操作的均摊时间复杂度为 O ( l o g n ) O(logn) O(logn)其中 n n n 是调用 add 的次数因为每个区间最多只会被加入和删除一次单词加入和删除的时间复杂度为 O ( l o g n ) O(logn) O(logn)。单次 add 的复杂度最差为 O ( n × l o g n ) O(n \times logn) O(n×logn)。
空间复杂度 O ( n ) O(n) O(n)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
