python - 计算未被任何一组区间覆盖的最小正整数

Question

几周前有人在这里发布了这个问题，但它看起来非常像没有事先研究的家庭作业，OP 在收到一些反对票后立即将其删除。

虽然这个问题本身很有趣，但我已经考虑了一个星期但没有找到令人满意的解决方案。希望有人能提供帮助？

问题如下:给定一个包含 N 个整数区间的列表，其边界可以取从 0 到 N³ 的任何值，找到最小的整数 i 使得 i 不属于任何输入区间。

例如，如果给定列表 [3,5] [2,8] [0,3] [10,13] (N = 4) ，算法应返回 9。

我能想到的最简单的解决方案在 O(n log(n)) 中运行，包括三个步骤:

1. 通过增加下限对区间进行排序
2. • 如果最小下界>0，则返回0；
   • 否则重复将第一个区间与第二个区间合并，直到第一个区间(比如 [a, b])不接触第二个区间(比如 [c, d]) — 也就是说，直到 b + 1 < c，或者直到只有一个区间。
3. 返回 b + 1

这个简单的解决方案在 O(n log(n)) 中运行，但是原始发帖人写道该算法应该在 O(n) 中运行。 如果间隔已经排序，那是微不足道的，但是 OP 给出的示例包括未排序的间隔。 我想这一定与 N³ 界限有关，但我不确定是什么……散列？线性时间排序？欢迎提出想法。

---

这是上述算法的粗略 python 实现:

def merge(first, second):
    (a, b), (c, d) = first, second
    if c <= b + 1:
        return (a, max(b, d))
    else:
        return False

def smallest_available_integer(intervals):
    # Sort in reverse order so that push/pop operations are fast
    intervals.sort(reverse = True)

    if (intervals == [] or intervals[-1][0] > 0):
        return 0

    while len(intervals) > 1:
        first = intervals.pop()
        second = intervals.pop()

        merged = merge(first, second)
        if merged:
            print("Merged", first, "with", second, " -> ", merged)
            intervals.append(merged)
        else:
            print(first, "cannot be merged with", second)
            return first[1] + 1

print(smallest_available_integer([(3,5), (2,8), (0,3), (10,13)]))

输出:

Merged (0, 3) with (2, 8)  ->  (0, 8)
Merged (0, 8) with (3, 5)  ->  (0, 8)
(0, 8) cannot be merged with (10, 13)
9

Answer 1

详细说明@mrip 的评论:您可以使用您描述的确切算法但更改排序算法的工作方式，在 O(n) 时间内完成此操作。

通常，基数排序使用基数 2:根据元素的位是 0 还是 1，将元素分为两个不同的桶。每一轮基数排序需要时间 O(n)，并且每个位有一轮最大的数字。调用那个最大的数字 U，这意味着时间复杂度是 O(n log U)。

但是，您可以将基数排序的基数更改为其他基数。使用基数 b，每一轮都需要时间 O(n + b)，因为初始化和遍历桶需要时间 O(b)，将元素分配到桶中需要时间 O(n)。然后有 log_b U 轮。这给出了 O((n + b)log_b U) 的运行时间。

这里的技巧是，由于最大数 U = n³，您可以设置 b = n 并使用以 n 为底的基数排序。轮数现在是 log_n U = log_n n³ = 3 并且每轮需要 O(n) 时间，所以总对数字进行排序的工作是 O(n)。更一般地说，您可以在时间 O(kn) 内对 [0, n^k) 范围内的任何 k 的数字进行排序。如果k是一个固定常数，这是O(n)时间。

结合你原来的算法，这个问题在时间 O(n) 内解决了。

希望这对您有所帮助!