Geek asks and answers

How to find the largest gap in a vector in O (n) time?

You are given the location of various cars on the same lane on the highway, which doubles to a vector, in a certain order. How can you find the largest gap between neighboring cars in O (n) time?

It seems like sorting and then checking is a simple solution, but of course this is not linear.

+5
source share
2 answers

Divide the vector in n + 1 identical sized buckets. For each such bucket, store the maximum and minimum values, all other values ​​can be discarded. Due to the pigeon hole principle, at least one of these parts is empty, therefore, the values ​​of not minimum / not maximum value in both parts do not affect the result.

; .

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.

+7

ipc- My 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

tuple bucket, None, . , ( , ).

, .

0

More articles:


All Articles