您将获得一个连续间隔数组,即{ [a,b],[b,c],[c,d],...,[g,h],[h,i] }
给定一个n m k类型的查询,我们需要输出包含k的n,m (inclusive, 1-based indexing)之间的间隔数。
我的方法:(天真地检查n,m和keeping a counter之间的所有间隔。)
如果m-n和查询数很小,则此方法有效,但对于较大的n,m值和多个查询而言,此方法的效率非常低。
但是,如果数组中给定的间隔太大,这也会失败,因为构建dp数组需要更长的时间。
我如何解决这个问题,或者有没有一种我缺少的更简单的方法?
任何提示都会有帮助。
示例:
数组:{ [1,3],[3,2],[2,1],[1,5],[5,3] }
查询:{ 1 2 2 }、{ 1 3 3 }、{ 2 2 4 }
输出:{ 2 }、{ 2 }、{ 0 }
发布于 2020-03-09 15:47:03
我会用下面的方法解决这个问题。
首先,我将介绍表单的另一个数据结构数组:
[(ai,bi,ci)]哪里
ai - interval start
bi - interval end
ci - count of intervals of original sequence hitting interval [ai,bi]
ai < bi
a(i+1) = bi因此,这种新的数据结构覆盖了原始结构的整个范围,它正在增加,并且具有原始区间的期望计数。
现在,要找到计数,我们只需要k并执行某种二进制搜索来找到间隔。
https://stackoverflow.com/questions/60594643
复制相似问题