【教3妹学编程-算法题】统计区间中的整数数目

2023-12-16 10:34:08

插: 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。
坚持不懈,越努力越幸运,大家一起学习鸭~~~

吃瓜

2哥 : 3妹早啊,大周末的起这么早,在干嘛呢?
3妹:没什么事,随便上上网,2哥,你有没有看到网上“董宇辉小作文事件”
2哥 : 看到了,董宇辉是个很有才华的人。他反对饭圈文化,文案有自己写的,也有小编写的
3妹:是啊,本来感觉事情不大,就是员工内部矛盾,没想到现在闹这么大啦!
2哥 : 甄选的CEO竟然说董宇辉的工资待遇,这不是没文矛盾嘛。
3妹:不知道这件事会如何收场,2哥你觉得呢?
2哥 : 我统计了下网上的几种说法:1、离职创业。 2、离职去其他家。
3妹:切, 网上统计的不准确啊。
2哥:哎,我们还是坐等后续吧, 不过真心希望董宇辉的才华不要被埋没。
3妹:说到统计,我今天倒是看到了一个关于统计的题目,让我们来做一下吧:

考考你

题目:

给你区间的 空 集,请你设计并实现满足要求的数据结构:

新增:添加一个区间到这个区间集合中。
统计:计算出现在 至少一个 区间中的整数个数。
实现 CountIntervals 类:

CountIntervals() 使用区间的空集初始化对象
void add(int left, int right) 添加区间 [left, right] 到区间集合之中。
int count() 返回出现在 至少一个 区间中的整数个数。
注意:区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。

示例 1:

输入
[“CountIntervals”, “add”, “add”, “count”, “add”, “count”]
[[], [2, 3], [7, 10], [], [5, 8], []]
输出
[null, null, null, 6, null, 8]

解释
CountIntervals countIntervals = new CountIntervals(); // 用一个区间空集初始化对象
countIntervals.add(2, 3); // 将 [2, 3] 添加到区间集合中
countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中
countIntervals.count(); // 返回 6
// 整数 2 和 3 出现在区间 [2, 3] 中
// 整数 7、8、9、10 出现在区间 [7, 10] 中
countIntervals.add(5, 8); // 将 [5, 8] 添加到区间集合中
countIntervals.count(); // 返回 8
// 整数 2 和 3 出现在区间 [2, 3] 中
// 整数 5 和 6 出现在区间 [5, 8] 中
// 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中
// 整数 9 和 10 出现在区间 [7, 10] 中

提示:

1 <= left <= right <= 10^9
最多调用 add 和 count 方法 总计 10^5 次
调用 count 方法至少一次

思路:

思考

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

java代码:

class CountIntervals {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    int cnt = 0;

    public CountIntervals() {

    }
    
    public void add(int left, int right) {
        Map.Entry<Integer, Integer> interval = map.floorEntry(right);
        while (interval != null && interval.getValue() >= left) {
        int l = interval.getKey(), r = interval.getValue();
            left = Math.min(left, l);
            right = Math.max(right, r);
            cnt -= r - l + 1;
            map.remove(l);
            interval = map.floorEntry(right);
        }
        cnt += (right - left + 1);
        map.put(left, right);
    }
    
    public int count() {
        return cnt;
    }
}

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