2023.12.16力扣每日一题——统计区间中的整数数目

2023.12.16力扣每日一题——统计区间中的整数数目

2023.12.16

• • • 题目来源
    • 我的题解
    • • 方法一 线段树（借鉴官方题解评论区 知白守黑）

题目来源

力扣每日一题；题序：2276

我的题解

方法一 线段树（借鉴官方题解评论区 知白守黑）

用一棵平衡二叉搜索树维护插入的区间，树中的区间两两不相交。当插入一个新的区间时，需要找出所有与待插入区间有重合整数的区间，将这些区间合并成一个新的区间后插入平衡树里。间隔包含两个属性，左端点 l 和右端点 r，其中左端点在树中参与排序。当插入一个新的间隔 add(left,right)时，需要找到树中的最大的间隔 interval满足：interval.l≤right，这个是可能与待插入的间隔相交的最大的间隔，如果相交，则将它们合并，并且继续寻找下一个这样的间隔，直到不存在这样的间隔或者找到的间隔与待插入的间隔不相交。同时用一个整数 cnt 维护树中的间隔覆盖的整数，当调用 count时，直接返回即可。

时间复杂度：add 的均摊时间复杂度为 O(log⁡n)，其中 n是调用 add的次数，因为每个区间最多只会被加入和删除一次，单次加入和删除的时间复杂度是 O(log⁡n)。单次 addtextit{add}add 的复杂度最差情况是 O(n×log⁡n)。count 的时间复杂度是 O(log⁡1)。
空间复杂度：O(1)

public class CountIntervals {TreeMap<Integer, 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 <= (key)) {//当它们区间有重叠时left = Math.min(left, key);right = Math.max(right, (key));cnt -= ((key) - key) + 1;//合并区间之后,要减去原来加上去的值ve(key);//移除原区间key = map.floorKey(right);}cnt += (right - left) + 1;map.put(left, right);}public int count() {return cnt;}}

困难题……不会啦，这里搬官方题解和评论区大佬的代码

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~