Jak znaleźć największą lukę w wektorze w czasie O (n)?

Question

Dostajesz lokalizacje różnych samochodów na tym samym torze na autostradzie, która podwaja się do wektora, w dowolnej kolejności. Jak znaleźć największą lukę między sąsiednimi samochodami w czasie O (n)?

Wygląda na to, że prostym rozwiązaniem byłoby sortowanie, a następnie sprawdzanie, ale oczywiście nie jest to liniowe.

Answer 1

Podziel wektor w n + 1 wiadrach o jednakowej wielkości. Dla każdego takiego segmentu przechowuj wartość maksymalną i minimalną, wszystkie pozostałe wartości można odrzucić. Ze względu na zasadę fałszowania przynajmniej jedna z tych części jest pusta, więc wartości inne niż minimalne w obu częściach nie mają wpływu na wynik.

Następnie przejdź przez wiadra i obliczyć odległość do następnej i poprzedniej niepustej łyżki i zrób maksimum; to jest końcowy wynik.

Przykład z n = 5 i wartościami 5,2,20,17,3. Minimum to 2, maksymalnie 20 => wielkość wiadro (20-2)/5 = 4

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

różnice: 2-5, 5-17, 17-20. Maksimum to 5-17.

Answer 2

My Python wdrożenie rozwiązania IPC:

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 

używam tuple elementów w wiaderku, None jeśli pusty. W ostatniej części eliminuję zapobiegawczo wszelkie pozostałe puste wiadra przypisując je poprzedniej (działa to, ponieważ pierwsza z nich jest gwarantowana, że ​​nie jest pusta).

Zwróć uwagę na specjalny przypadek, gdy wszystkie elementy są równe.