如何在O(n)时间内找到向量中最大的间隙？

Question

您会收到一些汽车在高速公路上的位置，这些位置表示为双精度浮点数存储在一个向量中，但没有特定的顺序。如何以O(n)时间复杂度找到相邻汽车之间的最大间隔？

看起来简单的解决方案是先排序，然后检查，但是显然这不是线性时间复杂度。

- Ashley Pinkman

---

O(n) 时间复杂度，需要多少空间？ - Jon

在向量中，(n) 表示元素的数量？是的，这可以通过一个相当基本的循环完成。 - Mats Petersson

@MatsPetersson - 但他要求一个漂亮的C++循环。 - Robᵩ

这是我遇到的一个面试问题。我假设空间是无限的。 - Ashley Pinkman

@mats，向量中的邻居不是高速公路上的邻居，它们没有排序。似乎不能在一次迭代中轻松完成？ - Scotch

这里是解决最大间隔问题的方案。 - user703016

Answer 1

将向量分成n+1个大小相等的桶。 对于每个这样的桶，存储最大值和最小值，所有其他值可以丢弃。 由于鸽笼原理，其中至少一个部分为空，因此任一部分中的非最小/非最大值对结果没有影响。

然后，遍历桶并计算到下一个和前一个非空桶的距离，并取最大值； 这是最终结果。

以n=5和值为5,2,20,17,3的示例。 最小值为2，最大值为20 => 桶大小为（20-2）/ 5 = 4。

Bucket:   2    6    10    14     18     20
Min/Max:   2-5   -    -     17,17  20,20

差异: 2-5, 5-17, 17-20. 最大值为 5-17。

- ipc

---

我不太明白，您能再详细解释一下吗？ - Ashley Pinkman

向量应该如何分成n+1部分？ - aioobe

你的意思是“取最大值和最小值，创建n+1个桶 - 第i个桶负责一个区间 [i*(max-min)/(n+1), (i+1)*(max-min)/(n+1)]”。 - lopek

这个对我来说太高深了。 :-D - जलजनक

我现在明白了。希望原帖作者也能理解。 - जलजनक

Answer 2

我对ipc的解决方案进行了Python实现：

def maximum_gap(l):
    n = len(l)
    if n < 2:
        return 0
    (x_min, x_max) = (min(l), max(l))
    if x_min == x_max:
        return 0
    buckets = [None] * (n + 1)
    bucket_size = float(x_max - x_min) / n
    for x in l:
        k = int((x - x_min) / bucket_size)
        if buckets[k] is None:
            buckets[k] = (x, x)
        else:
            buckets[k] = (min(x, buckets[k][0]), max(x, buckets[k][1]))
    result = 0
    for i in range(n):
        if buckets[i + 1] is None:
            buckets[i + 1] = buckets[i]
        else:
            result = max(result, buckets[i + 1][0] - buckets[i][1])
    return result

assert maximum_gap([]) == 0
assert maximum_gap([42]) == 0
assert maximum_gap([1, 1, 1, 1]) == 0
assert maximum_gap([1, 2, 3, 4, 6, 8]) == 2
assert maximum_gap([5, 2, 20, 17, 3]) == 12

我使用元组来表示桶的元素，如果为空则使用None。在最后一部分，我通过将剩余的空桶分配给前一个桶来预先消除任何剩余的空桶（这是可行的，因为第一个桶保证不为空）。

请注意当所有元素都相等时的特殊情况。

- Aristide