计算任何一组间隔未涵盖的最小正整数

Question

几个星期前有人在这里发布了这个问题,但是在没有事先研究的情况下看起来非常像家庭作业,并且在得到一些downvotes之后,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),并且每个最大数字的位有一个回合.调用最大的nunber 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并使用base-n基数排序.轮数现在是log _n U = log _n n ³ = 3并且每轮需要O(n)时间,因此对数字进行排序的总工作量是O(n).更一般地,对于任何k ,您可以在时间O(kn)的[0,n ^k ] 范围内对数字进行排序.如果k是固定常数,则为O(n)时间.

结合您的原始算法,这解决了时间O(n)的问题.

希望这可以帮助!