0

给定一个区间列表（这里显示了它们的索引）：

0: 1,3
1: 0,4
2: 5,7
3: 6,9
4: 2,8

然后从列表索引中给出任意进出，有没有一种好方法可以从包含的相应间隔中确定最小值和最大值？

例如：0,4会给你0,9。 2,3会给你5,9。

我目前的解决方案涉及迭代范围内的每个间隔，在入点上保持最小值，在出点上保持最大值。想知道是否存在算法技术的数据结构，当间隔列表很长时，我会忽略它以使其更快。由于间隔列表没有改变，也许我可以预先创建一些模型来以不同的方式表示数据？

4

2 回答 2

2

一种简单的方法是使用树形结构。树的根将具有整个列表的最小值/最大值。然后它将有两个孩子，它们给出前半部分和后半部分的最小值/最大值等。这将允许您使用 O(log(n)) 搜索算法，其中 n 是整个区间列表的大小。

首先，您构建树。这可以通过将区间列表分成两部分并为每个子区间制作一棵树来递归完成：

def makeTree(begin,end,intervals):
  if end==begin:
    return None
  if end==begin+1:
    return Node(begin,end,intervals[begin],None,None)
  partition=(begin+end)/2
  left=makeTree(begin,partition)
  right=makeTree(partition,end)
  range=combineRanges(rangeOf(left),rangeOf(right))
  return Node(begin,end,range,left,right)

一旦你有了树，你可以将树的根传递给这个函数：

def findRange(node,begin,end):
  # If the node's range doesn't intersect the range you are looking for, 
  # then you don't have to look any deeper.
  if node is None or begin>=node.end or end<=node.begin:
    return None
  # If the node's range is completely inside the range you are looking for, then
  # you also don't need to look any deeper.
  if begin<=node.begin and end>=node.end:
    return node.range
  # Otherwise, check each child.
  left_range=findRange(node.left,begin,end)
  right_range=findRange(node.right,begin,end)
  # And return the combined result.
  return combineRanges(left_range,right_range)

请注意，我使用的是半开区间，对于区间中的任何 x，begin <= x < end。这只是使代码更干净一些。

于 2012-12-17T05:28:39.803 回答
1

很容易看出，每个区间实际上表示一个最小值和一个最大值。

所以问题就变成了：给你 2 个数组，找到任何指定索引范围的最小值和最大值。

发现最小值和最大值相似，所以我们在这里讨论最小值。

首先，如前所述，可以使用Segment tree@Vaughn Cato轻松完成。

而且实际上我们不需要使用如此强大的数据结构，例如Segment tree，还有另一种特定的算法可以解决这个问题，称为Range Minimum Query。

顺便说一句，我写了一篇关于 的帖子RMQ，请参阅http://attiix.com/2011/08/22/4-ways-to-solve-%c2%b11-rmq/。

于 2012-12-17T08:06:03.847 回答