Làm thế nào để bạn tìm thấy khoảng cách lớn nhất trong một vector trong thời gian O (n)?

Question

Bạn được cung cấp các vị trí của nhiều loại xe khác nhau trong cùng một làn đường trên đường cao tốc như đôi với một véc tơ, không theo thứ tự cụ thể. Làm thế nào bạn có thể tìm thấy khoảng cách lớn nhất giữa các xe lân cận trong thời gian O (n)?

Có vẻ như một giải pháp đơn giản sẽ là sắp xếp, sau đó kiểm tra, nhưng tất nhiên điều này không phải là tuyến tính.

Answer 1

Chia véc tơ thành n + 1 nhóm có kích thước bằng nhau. Đối với mỗi nhóm như vậy, lưu trữ giá trị tối đa và tối thiểu, tất cả các giá trị khác có thể được loại bỏ. Do nguyên lý pigeonhole, ít nhất một trong những phần đó trống rỗng, do đó, các giá trị không tối thiểu/không tối đa trong cả hai phần không có ảnh hưởng đến kết quả.

Sau đó, chuyển qua các nhóm và tính toán khoảng cách tới nhóm tiếp theo và nhóm không trống trước đó và lấy tối đa; đây là kết quả cuối cùng.

Ví dụ với n = 5 và giá trị 5,2,20,17,3. Tối thiểu là 2, tối đa là 20 => kích thước thùng là (20-2)/5 = 4.

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

Sự khác biệt: 2-5, 5-17, 17-20. Tối đa là 5-17.

Answer 2

My Python thực hiện giải pháp ipc của:

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 

tôi sử dụng một tuple cho các yếu tố xô của, None nếu có sản phẩm nào. Trong phần cuối cùng, tôi loại bỏ preemptively bất kỳ thùng rỗng còn lại bằng cách gán nó cho cái trước đó (tác phẩm này, vì cái đầu tiên được đảm bảo là không trống).

Lưu ý trường hợp đặc biệt khi tất cả các phần tử đều bằng nhau.