文化建设设计公司网站,摄影作品欣赏网站推荐,wordpress本地服务器,做网站可以在哪儿接活2023.12.16 题目来源我的题解方法一 线段树#xff08;借鉴官方题解评论区 知白守黑#xff09; 题目来源
力扣每日一题#xff1b;题序#xff1a;2276
我的题解
方法一 线段树#xff08;借鉴官方题解评论区 知白守黑#xff09; 用一棵平衡二叉搜索树维护插入的区间… 2023.12.16 题目来源我的题解方法一 线段树借鉴官方题解评论区 知白守黑 题目来源
力扣每日一题题序2276
我的题解
方法一 线段树借鉴官方题解评论区 知白守黑 用一棵平衡二叉搜索树维护插入的区间树中的区间两两不相交。当插入一个新的区间时需要找出所有与待插入区间有重合整数的区间将这些区间合并成一个新的区间后插入平衡树里。间隔包含两个属性左端点 l 和右端点 r其中左端点在树中参与排序。当插入一个新的间隔 add(left,right)时需要找到树中的最大的间隔 interval满足interval.l≤right这个是可能与待插入的间隔相交的最大的间隔如果相交则将它们合并并且继续寻找下一个这样的间隔直到不存在这样的间隔或者找到的间隔与待插入的间隔不相交。同时用一个整数 cnt 维护树中的间隔覆盖的整数当调用 count时直接返回即可。 时间复杂度add 的均摊时间复杂度为 O(logn)其中 n是调用 add的次数因为每个区间最多只会被加入和删除一次单次加入和删除的时间复杂度是 O(logn)。单次 add\textit{add}add 的复杂度最差情况是 O(n×logn)。count 的时间复杂度是 O(log1)。 空间复杂度O(1) public class CountIntervals {TreeMapInteger, Integer map;int cnt;public CountIntervals() {map new TreeMap();cnt 0;}public void add(int left, int right) {Integer key map.floorKey(right);//返回小于等于right的最大的那个keywhile (key ! null left map.get(key)) {//当它们区间有重叠时left Math.min(left, key);right Math.max(right, map.get(key));cnt - (map.get(key) - key) 1;//合并区间之后,要减去原来加上去的值map.remove(key);//移除原区间key map.floorKey(right);}cnt (right - left) 1;map.put(left, right);}public int count() {return cnt;}}困难题……不会啦这里搬官方题解和评论区大佬的代码
有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
