2023.12.16力扣每日一题

2023-12-18 21:05:51

题目来源

力扣每日一题;题序:2276

我的题解

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

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

时间复杂度:add 的均摊时间复杂度为 O(log?n),其中 n是调用 add的次数,因为每个区间最多只会被加入和删除一次,单次加入和删除的时间复杂度是 O(log?n)。单次 add\textit{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的最大的那个key
        while (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;
    }

}

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

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

文章来源:https://blog.csdn.net/weixin_42075274/article/details/135069376
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。