ম্যাক্সিমাম গ্যাপ সমস্যা
একটি আনসর্টেড অ্যারে দেওয়া আছে। সর্ট করা অবস্থায় দুটি egymানуюপস্থিত উপাদানের মধ্যে সর্বোচ্চ পার্থক্য (গ্যাপ) বের করতে হবে। অ্যারেতে ২টির কম উপাদান থাকলে ০ ফেরত দিন।
উদাহরণ: [12,3,9,1,17] → সর্টেড: [1,3,9,12,17] → গ্যাপস: ২, ৬, ৩, ৫ → সর্বোচ্চ: ৬
সমাধানের পদ্ধতি (বাকেট সোর্ট / পিজনহোল প্রিন্সিপল)
minVal, maxValবের করুন- ন্যূনতম সম্ভব গ্যাপ:
gap = ceil((maxVal - minVal) / (n-1)) n-1টি বাকেট তৈরি করুন, প্রতিটি বাকেটেminএবংmaxরাখুন- প্রতিটি সংখ্যা (ছাড়া
minVal, maxVal) বাকেটে বিতরণ করুন:idx = (num - minVal) / gap - খালি বাকেটগুলো স্কিপ করে সংলগ্ন নন-এম্পটি বাকেটগুলোর মাঝপথের গ্যাপ চেক করুন
- শেষে
maxVal - lastBucketMaxও চেক করুন
সময় জটিলতা: O(n), স্পেস: O(n)
C++ কোড উদাহরণ
[12,3,9,1,17]
আউটপুট
6
