1

我有两个这种形式的范围数组：

wanted = {[10, 15], [20, 25]}
cut = {[5, 12], [22, 24]}

wanted由两个元素（范围）组成的数组也是如此-[10, 15]和[20, 25].

这两个数组中的每一个都满足以下条件：

  1. 它按每个整数范围中的第一个值排序
  2. 范围永远不会重叠（例如[10, 15]，[15, 25]不可能）
  3. 这也意味着每个范围在数组中都是唯一的（不[1, 5]，，[1, 5]）
  4. 如果一个范围只有一个整数宽，它将显示为[5, 5]（开始和结束相等）

我现在想获得一个范围数组，其中所有范围cut都已从wanted.

result = {[13, 15], [20, 21], [25, 25]}

是否有一些比下面更好/更容易/更快的出色算法？

对于 中的每个元素wanted，将该元素与一个又一个元素从 from 进行比较，cut直到元素 fromcut结束于元素 from 之上wanted。

4

2 回答 2

2

假设有n元素 inwanted和m元素 in cut。

以下是O(m + n)执行所需任务的算法：

j = 1
result = {}
for i = 1:n
  // go to next cut while current cut ends before current item
  while j <= m && cut[j].end < wanted[i].start
    j++
  // cut after item, thus no overlap
  if j > m || cut[j].start > wanted[i].end
    result += (wanted[i].start, wanted[i].end)
  else // overlap
    // extract from start to cut start
    if cut[j].start > wanted[i].start
      result += (wanted[i].start, cut[j].start-1)
    // extract from cut end to end
    if cut[j].end < wanted[i].end
      result += (cut[j].end+1, wanted[i].end)
      j++

请注意，渐近地，您不能做得比 更好O(m + n)，因为证明您需要查看每个元素（在最坏的情况下）应该相当容易。

于 2013-05-17T07:58:51.153 回答
0

wanted最大的尺寸cut是多少？比较“第一个元素来自wanted”与“所有来自cut”将花费 O(n^2) 运行时间，即如果数组很大，则非常慢。

并行处理每个数组会快得多，直到到达两者的末尾，例如“合并”。

于 2013-05-16T18:56:34.680 回答