ओ (एन) समय में वेक्टर में सबसे बड़ा अंतर आपको कैसे मिलता है?

Question

आपको किसी भी विशेष क्रम में एक वेक्टर के लिए युगल के रूप में एक राजमार्ग पर एक ही लेन में विभिन्न कारों के स्थान दिए जाते हैं। ओ (एन) समय में पड़ोसी कारों के बीच आप सबसे बड़ा अंतर कैसे पा सकते हैं?

ऐसा लगता है कि एक सरल समाधान की तरह जांचना होगा, लेकिन निश्चित रूप से यह रैखिक नहीं है।

Answer 1

वेक्टर को एन + 1 समान रूप से आकार वाली बाल्टी में विभाजित करें। ऐसी प्रत्येक बाल्टी के लिए, अधिकतम और न्यूनतम मान स्टोर करें, अन्य सभी मानों को त्याग दिया जा सकता है। कबूतर सिद्धांत के कारण, उनमें से कम से कम एक भाग खाली है, इसलिए किसी भी हिस्से में गैर-न्यूनतम/गैर-अधिकतम मान परिणाम के लिए प्रभाव नहीं डालते हैं।

फिर, बाल्टी पर जाएं और अगली और पिछली गैर-खाली बाल्टी की दूरी की गणना करें, और अधिकतम लें; यह अंतिम परिणाम है।

एन = 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 है।

Answer 2

आईपीसी के समाधान के मेरे अजगर कार्यान्वयन:

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 उपयोग करते हैं, None अगर खाली। आखिरी हिस्से में, मैं इसे पिछले एक को असाइन करके किसी भी शेष खाली बाल्टी को पूर्ववत कर देता हूं (यह काम करता है, क्योंकि पहले व्यक्ति को खाली होने की गारंटी है)।

विशेष मामले नोट करें जब सभी तत्व बराबर हैं।