苏州建网站要多少钱,那个网站上有打码的任务做,音乐制作,苏宁易购电商网站建设需求分析【LetMeFly】2276.统计区间中的整数数目
力扣题目链接#xff1a;https://leetcode.cn/problems/count-integers-in-intervals/
给你区间的 空 集#xff0c;请你设计并实现满足要求的数据结构#xff1a;
新增#xff1a;添加一个区间到这个区间集合中。统计#xff1…【LetMeFly】2276.统计区间中的整数数目
力扣题目链接https://leetcode.cn/problems/count-integers-in-intervals/
给你区间的 空 集请你设计并实现满足要求的数据结构
新增添加一个区间到这个区间集合中。统计计算出现在 至少一个 区间中的整数个数。
实现 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 109最多调用 add 和 count 方法 总计 105 次调用 count 方法至少一次
方法一二分
使用一个变量cnt记录区间中的整数个数使用一个数据结构ma记录所有的区间。其中数据结构要满足能在 O ( log n ) O(\log n) O(logn)的时间内找到新区间应插入的位置。
如果询问区间中整数的个数就直接返回cnt如果要添加区间 [ l e f t , r i g h t ] [left, right] [left,right]就在ma中二分等方式找到第一个要合并的区间的位置不断向后遍历直到区间合并进来为止。 合并过程中记得维持数据结构性质不变、更新区间中整数个数cnt
以上。本题思路不难实现起来有很多细节要考虑
时间复杂度单次查询操作时间复杂度 O ( 1 ) O(1) O(1)单次合并操作时间复杂度平均 O ( log n ) O(\log n) O(logn)因为每个区间最多呗背合并一次空间复杂度 O ( n ) O(n) O(n)其中 n n n是不同区间的个数
AC代码
C
class CountIntervals {
private:mapint, int ma;int cnt;
public:CountIntervals() {cnt 0;}void add(int left, int right) {mapint, int::iterator it ma.upper_bound(right);if (it ! ma.begin()) {it--;}while (it ! ma.end() it-first right it-second left) {int leftInmap it-first, rightInmap it-second;cnt - rightInmap - leftInmap 1;left min(left, leftInmap), right max(right, rightInmap);ma.erase(it);it ma.upper_bound(right);if (it ! ma.begin()) {it--;}}ma[left] right;cnt right - left 1;}int count() {return cnt;}
};同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/135036679
