时间戳

首页 > 解决方案 > 在给定范围内查找缺失范围

algorithm - 在给定范围内查找缺失范围

问题描述

当给出主范围并给出所有子范围时，我们需要找到缺失的范围。主要范围：[-10, 10]

子范围： [-10, -5] , [-4, -3], [-2, 3], [7, 10]

假设：

1) 范围值可以达到 2^63。

2）子范围不会重叠，它们的顺序可以不同。例如：可以是 [-10, -5],[7, 10], [-2, 3], [-4, -3]

在这里找到缺失范围的最佳算法是什么？

标签： algorithmdata-structures

解决方案

假设区间是未排序的，我看不到避免排序成本，因为每个区间都可以是单例 ( [n,n])。该成本可以O(n log n)用于比较排序或O(n)基数排序。从现在开始，让我们假设输入区间已排序并且不包含重叠。这是一个O(n)单程 Python 实现：

xs =  [[-10, -5] , [-4, -3], [-2, 3], [7, 10]]
bounds = (-10, 10)
missing = list()

# pre-processing
xs_sorted = sorted(xs)

# pre-processing a missing range on the lower bound
if bounds[0] < xs_sorted[0][0]:
  missing.append((bounds[0], xs_sorted[0][0]-1))

def f_reduce(a, b):
  if a[1] + 1 == b[0]:
    # merge contiguous intervals
    return (a[0], b[1])
  else:
    # gap detected; add the gap to the missing range list
    # and move to the next value
    missing.append((a[1]+1, b[0]-1))
    return b

from functools import reduce
reduce(f_reduce, xs_sorted)

# post-processing on a missing range on the upper bound
if bounds[1] > xs_sorted[-1][1]:
  missing.append((xs_sorted[-1][1]+1, bounds[1]))

print(missing)
# [(4, 6)]

方法是使用reduce带有臭味副作用的功能样式。当函数f_reduce遇到两个区间(a, b)and(c, d)时，我们返回一个复合区间(a, d)if b + 1 == c。否则，检测并存储间隙；返回的区间是(c, d)。当间隔的两个极端范围内出现间隙时，预处理和后处理步骤正在处理令人讨厌的情况。

推荐阅读