今天学习了一下重复区间问题
问题一,求最大重复区间个数
1.数据是静态的:
这个问题的最大重叠点一定出现在端点上。更进一步说,它一定可以出现在左端点上。 对区间端点进行排序,N个区间排序后的端点数量为2N。 遍历端点列表,左端点+1,右端点-1,记录遍历过程中的最大值,即为最大重复区间个数。 2.数据是动态的: 参考:算法导论中文版(原书第二版)190页思考题14-1 http://bbs.csdn.net/topics/300181969
问题二,求最长重复区间长度
首先还是将各行数据整理成x<y的标准形式,然后:
1)将各区间按照x从小到大排序(对于x(i)=x(i+1)这种情况可以优化,只保留较“长”的区间即可。比方说 此时有y(i)>y(i+1),那我们只需要保留[x(i),y(i)]区间,而对[x(i+1),y(i+1)]可以省略)——这一步需要O(n*logn);
2)将各区间数据进行整理,保持y严格递增,同时记录下被“删除”区间的最大长度max——这一步需要O(n);
(例如对于[1,5][2,4][3,5][4,7][5,6],为了保证y严格递增,需要删除某些区间,只剩下[1,5][4,7]
这一步的实际含义是统计区间相互“包含”的情况中,最长的“被包含”区间是多少);
3)经过前两步之后,在剩下的区间序列中,不管x还是y都是保持严格递增的(从而保证剩下的区间中不会再出现相互“包含”的情况)。
此时最长的重叠区间只可能有相邻的两个区间产生,遍历统计并更新max——这一步需要O(n)
从而整体只需要O(n*logn)的复杂度,主要花费在排序上。
如果对于已经排好序的数据而言,O(n)线性时间内即可完成。
分享到:
相关推荐
通过移位和逻辑运算,快速生成给定区间的不重复随机数。 形象地说就是随机打乱值的顺序。 发现网上其它的方法都太慢了,又刚好想到这个方法, 就传上来了。
青蒿素高含量地区黄花蒿种质资源的简单重复序列区间归类.pdf
帆软报表填报校验,数据插入时判断插入数据是否和数据库数据是否重复,不重复则插入,重复则显示提示信息“数据插入重复,请检查”,反之则插入成功,报表页面显示插入数据。
这是中科大软件学院算法导论的课程设计,是用c++实现的
差分区间主要用于解决一些需要对数组的某个区间进行增减操作的问题。它可以有效地减少重复计算的次数,提高程序的效率。 在C++中,可以使用数组来表示差分区间。假设有一个长度为n的数组a,我们可以通过另一个长度...
论文研究-基于正态分布... 与传统的逆向云算法不同, 该算法能够处理代表某一定性概念的区间数并能避免参数求取过程中的重复计算. 实验分析表明: 该算法可以以较高的精度还原云模型的三个数字特征值, 具有较高的实用性.
将第一个节点入栈,目前的区间和栈顶计算重叠,若重叠,则出栈将新合并的区间入栈,之后如此重复;否则不重叠时,将目前区间继续入栈,继续之后的循环。(排序后,目前节点
文章分析了平坦地形、近水平、缓倾斜赋存的大型露天煤矿分区开采时相邻条区间的直角缓帮、扇形、重新拉沟三种转向方式及其特点,推荐优先采用扇形转向方式进行条区间的过渡。当采用重新拉沟方式转向时,反向重新拉沟...
有限区间非线性系统的重复学习控制
冒泡排序重复地遍历列表,比较相邻元素并交换位置,直到列表已排序。 虽然这个例子很简单,但它展示了Python易读性较高的语法,以及标准库强大的随机数生成功能。冒泡排序算法也是很多初学者学习排序算法的起点。 所以,...
在 JavaScript 中,一般产生的随机数会重复,但是有时我们需要不重复的随机数,如何实现?下面就来讲解三种方法产生不重复的随机数,并进行比较,看那种方法效率高。方法一 思路:首先创建一个1到3000的数组,每次取...
C#生成指定范围内的不重复随机数 // Number随机数个数 // minNum随机数下限 // maxNum随机数上限 public int[] GetRandomArray(int Number,int minNum,int maxNum) { int j; int[] b=new int[Number]; Random r...
这一问题的核心其实就是产生不重复随机数的问题。首先想到的递归的方法,然后才发现Python中居然已经提供了此方法的函数,可以直接使用。具体代码如下: #生成某区间内不重复的N个随机数的方法 import random; #1、...
主要为大家详细介绍了C++生成不重复的随机整数,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
nboot 是一个标量,或最多两个正整数的向量,表示第一次和第二次引导的重复样本数。 bootfun是用@指定的函数句柄,或表示函数名称的字符串。 第三个和后面的输入参数是数据(列向量),用于创建 bootfun 的输入。 ...
用来随机生成两个2~100之间的随机数a和b,找出区间[a,b] (a)内的素数,并用列表保存,输出前5个素数和该5个素数的均值,保留两位小数。如果该区间内不足5个素数,重新生成区间并重复以上过程。以
2.Gif播放一半,弹出自定义动画,循环播放Gif任意区间帧动画。 3.tableView的headerView的伸缩变化。 下载地址:https://github.com/FighterLightning/GifImageAndImageChange.git 感觉有帮助,请不要吝啬你的...
686. 重复叠加字符串匹配 给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数,使得字符串...A 与 B 字符串的长度在1和10000区间范围内。 class Solution { public int repeatedStringMatch(String A, String B) {
找出一个区间中包含的离散周期函数的多少个值。 什么是离散周期函数? 周期函数是重复的函数。 离散函数是值不连接的函数。 离散周期函数的一个例子是日历上的“星期三”函数。 星期三是时间线上的离散值,它们每 ...