我想知道是否有比我提出的更有效的解决方案(还没有编码,但在底部描述了它的要点)。
编写一个函数calcNthSmallest(n,intervals),该函数将一个非负的int n和一个区间列表[a_1;b_1;::;a_m;b_m]作为输入,并在取所有具有重复的区间的并集时计算第n个最小数字(0-索引)。例如,如果间隔是1;5;2;4;7;9,则它们与重复的并集将是1; 2; 2; 3; 3; 4; 4; 5; 7; 8; 9。对于此间隔列表,第0个最小数字为1,第3个和第4个最小数字均为3。即使a_i;b_i非常大(如一万亿)并且有多个间隔,您的实现也应快速运行
我想要去做的方式是简单的解决方案,那就是创建并遍历联合数组。
发布于 2012-11-23 01:01:06
这个问题可以在O(N log N)中解决,其中N是列表中的间隔数,而不考虑间隔端点的实际值。
有效解决此问题的关键是将可能重叠的区间列表转换为不相交或相同的区间列表。在给定的示例中,只需要拆分第一个间隔:
{ [1,5], [2,4], [7,9]} =>
+-----------------+ +---+ +---+
{[1,1], [2,4], [5,5], [2,4], [7,9]}(不过,这并不是必须显式完成的:请参见下面的内容。)现在,我们可以对新的间隔进行排序,用计数替换重复项。由此,我们可以计算每个(可能重复的)间隔表示的值的数量。现在,我们只需要累加这些值来找出解决方案所在的区间:
interval count size values cumulative
in interval values
[1,1] 1 1 1 [0, 1)
[2,4] 2 3 6 [1, 7) (eg. from n=1 to n=6 will be here)
[5,5] 1 1 1 [7, 8)
[7,9] 1 3 3 [8, 11)我将累积值写成半开区间的列表,但显然我们只需要端点。然后,我们可以通过例如对累积值列表进行二进制搜索来找出哪个间隔保存值n,并且我们可以通过从n中减去间隔的开始,然后整数除以计数来计算出我们想要的间隔中的哪个值。
应该清楚的是,上表的最大大小是原始间隔数的两倍,因为每一行都必须在原始列表中某个间隔的开始或结束处开始和结束。如果我们将间隔写为半开而不是闭合,这将更加清楚;在这种情况下,我们可以断言表的精确大小将是端点集合中唯一值的数量。从这一点可以看出,我们实际上根本不需要表;我们只需要端点的排序列表(尽管我们需要知道每个值代表哪个端点)。我们可以简单地迭代该列表,保持活动间隔数的计数,直到我们达到我们想要的值。
下面是一个简单的python实现。这是可以改进的。
def combineIntervals(intervals):
# endpoints will map each endpoint to a count
endpoints = {}
# These two lists represent the start and (1+end) of each interval
# Each start adds 1 to the count, and each limit subtracts 1
for start in (i[0] for i in intervals):
endpoints[start] = endpoints.setdefault(start, 0) + 1
for limit in (i[1]+1 for i in intervals):
endpoints[limit] = endpoints.setdefault(limit, 0) - 1
# Filtering is a possibly premature optimization but it was easy
return sorted(filter(lambda kv: kv[1] != 0,
endpoints.iteritems()))
def nthSmallestInIntervalList(n, intervals):
limits = combineIntervals(intervals)
cumulative = 0
count = 0
index = 0
here = limits[0][0]
while index < len(limits):
size = limits[index][0] - here
if n < cumulative + count * size:
# [here, next) contains the value we're searching for
return here + (n - cumulative) / count
# advance
cumulative += count * size
count += limits[index][1]
here += size
index += 1
# We didn't find it. We could throw an error因此,正如我所说的,该算法的运行时间与区间的实际值无关;它只取决于区间列表的长度。由于排序的开销(在combineIntervals中),这个特定的解决方案是O(N log N)的;如果我们使用优先级队列而不是完全排序,我们可以在O(N)中构造堆,但对每个扫描的端点进行扫描O(log N)。除非N真的很大,而参数n的期望值相对较小,否则这将适得其反。不过,可能还有其他方法可以降低复杂性。
发布于 2012-11-22 22:23:16
Edit2:
这是对你的问题的另一种看法。
让我们以图形化的方式考虑间隔:
1 1 1 2 2 2 3
0-2-4--7--0--3---7-0--4--7--0
[-------]
[-----------------]
[---------]
[--------------]
[-----]当在下限上按升序排序时,我们可以得到类似于上面间隔列表([2;10];[4;24];[7;17];[13;30];[20;27])的内容。每一个下限都表示一个新间隔的开始,也标志着数字复制的另一个“水平”的开始。相反,上限标记了该级别的结束,并减少了一个级别的复制级别。因此,我们可以将上面的列表转换为以下列表:
[2;+];[4;+];[7;+][10;-];[13;+];[17;-][20;+];[24;-];[27;-];[30;-]其中,第一个值表示边界的等级,第二个值表示边界是下界(+)还是上界(-)。第n个元素的计算是通过跟随列表,当遇到下限或上限时提高或降低复制水平,并使用复制水平作为计数因子来完成的。
让我们再次以图形方式考虑列表,但将其作为直方图:
3333 44444 5555
2222222333333344444555
111111111222222222222444444
1 1 1 2 2 2 3
0-2-4--7--0--3---7-0--4--7--0上面的视图与第一个视图相同,所有间隔都是垂直排列的。1是第一个元素,2是第二个元素,依此类推。实际上,这里重要的是每个索引处的高度,对应于每个索引在所有区间的并集中重复的次数。
3333 55555 7777
2223333445555567777888
112223333445555567777888999
1 1 1 2 2 2 3
0-2-4--7--0--3---7-0--4--7--0
| | | | | | || | |我们可以看到,直方图块从区间的下界开始,在上界结束,或者在下界之前一个单位结束,因此新的符号必须进行相应的修改。
计算数字的第二步是O(n),总平均时间为O(nlog(n))。
下面是一个简单的OCaml实现,使用1和-1代替'+‘和'-’。
(* transform the list in the correct notation *)
let rec convert = function
[] -> []
| (l,u)::xs -> (l,1)::(u+1,-1)::convert xs;;
(* the counting function *)
let rec count r f = function
[] -> raise Not_found
| [a,x] -> (match f + x with
0 -> if r = 0 then a else raise Not_found
| _ -> a + (r / f))
| (a,x)::(b,y)::l ->
if a = b
then count r f ((b,x+y)::l)
else
let f = f + x in
if f > 0 then
let range = (b - a) * f in
if range > r
then a + (r / f)
else count (r - range) f ((b,y)::l)
else count r f ((b,y)::l);;
(* the compute function *)
let compute l =
let compare (x,_) (y,_) = compare x y in
let l = List.sort compare (convert l) in
fun m -> count m 0 l;;注意:-如果查找的数字大于间隔,则上面的函数将引发异常。下面的其他方法不考虑这种转角情况。详细说明: OCaml中使用的列表排序函数是合并排序,它的执行效率为O(nlog(n))。
编辑:
考虑到您可能有非常大的间隔,我最初给出的解决方案(见下文)远不是最优的。相反,我们可以通过转换列表来使事情变得更快:我们尝试通过搜索重叠的间隔列表来压缩间隔列表,并通过添加前缀interval、几倍于重叠的interval和后缀interval来替换它们。然后,我们可以直接计算列表中每个元素所覆盖的条目数量。查看上面的拆分(前缀、中缀、后缀),我们可以看到进行处理的最佳结构是二叉树。该树的节点可以可选地具有前缀和后缀。因此,该节点必须包含:
i in the nodei的重复次数,i下面所有间隔的左子树<代码>H221<代码>H122以上所有间隔的右子树<代码>D23<代码>H224<代码>F225有了这个结构,树就会自动排序。下面是一个包含该树的ocaml类型的示例。
type tree = Empty | Node of int * interval * tree * tree现在,转换算法归结为构建树。
此函数在其组件之外创建一棵树:
let cons k r lt rt =
the tree made of count k, interval r, left tree lt and right tree rt此函数以递归方式在树中插入间隔。
let rec insert i it =
let r = root of it
let lt = the left subtree of it
let rt = the right subtree of it
let k = the count of r
let prf, inf, suf = the prefix, infix and suffix of i according to r
return cons (k+1) inf (insert prf lt) (insert suf rt)一旦构建了树,我们对树进行预排序遍历,使用节点的计数来加速第n个元素的计算。
下面是我之前的回答。
以下是我的解决方案的步骤:
代码如下:
let lower i = lower bound of interval i
let upper i = upper bound of i
let il = sort of interval list
i <- 0
j <- lower (head of il)
loop on il:
i <- i + 1
let h = the head of il
let il = the tail of il
if upper h > j then push h to dq
if lower h > j then
il <- concat dq and il
j <- j + 1
dq <- empty
loop
if i = k then return j
loop当达到目标等级k时,返回值。
复杂度大致为O(k) + O(sort(l))。
发布于 2012-11-22 20:05:31
如果我没理解错你的问题,你想要在区间列表的并集中找到第k个最大的元素。如果我们假设列表的no =2,则问题是:在两个排序数组的并集中找到第k个最小元素(其中间隔2,5除了2到5{2,3,4,5}中的元素外什么都不是),这个解可以在(n+m)log(n+m) time (其中n和m是列表的大小)中求解。其中i和j是列表迭代器。
Maintaining the invariant
i + j = k – 1,
If Bj-1 < Ai < Bj, then Ai must be the k-th smallest,
or else if Ai-1 < Bj < Ai, then Bj must be the k-th smallest.有关详情,请参阅click here
现在的问题是,如果你没有lists=3列表
Maintaining the invariant
i + j+ x = k – 1,
i + j=k-x-1
The value k-x-1 can take y (size of third list, because x iterates from start point of list to end point) .
problem of 3 lists size can be reduced to y*(problem of size 2 list). So complexity is `y*((n+m)log(n+m))`
If Bj-1 < Ai < Bj, then Ai must be the k-th smallest,
or else if Ai-1 < Bj < Ai, then Bj must be the k-th smallest.因此,对于大小为n的列表问题,其复杂度是NP。
但是,是的,我们可以做一些小的改进,如果我们知道k<的大小(一些列表),我们可以从k+1th元素开始到结束(从我们的搜索空间),在那些大小大于k的列表中(我认为这对大k没有帮助).If有任何错误,请让我知道。
https://stackoverflow.com/questions/13507925
复制相似问题