ধরুন আমাদের কাছে nums নামে একটি সংখ্যার তালিকা আছে এবং আরেকটি মান k, আমাদেরকে তালিকার যেকোনো সাবলিস্টের বৃহত্তম গড় মান খুঁজে বের করতে হবে যার দৈর্ঘ্য কমপক্ষে k।
সুতরাং, যদি ইনপুটটি nums =[2, 10, -50, 4, 6, 6] k =3 এর মত হয়, তাহলে আউটপুট হবে 5.33333333, কারণ সাবলিস্ট [4, 6, 6]-এর গড় মান সবচেয়ে বেশি পি>
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
বাম :=সর্বনিম্ন সংখ্যা, ডানে :=সর্বাধিক সংখ্যা
-
s :=সূচক 0 থেকে k − 1 পর্যন্ত সমস্ত সংখ্যার যোগফল
-
large_avg :=s / k
-
যখন বামে <=ডানে, কর
-
মধ্য :=(বাম + ডান) / 2
এর পূর্ণসংখ্যা -
sum1 :=s, avg :=s/k, sum2 :=0, cnt :=0
-
i রেঞ্জ k থেকে সংখ্যার আকারের জন্য, করুন
-
যোগফল1 :=যোগফল1 + সংখ্যা[i]
-
যোগফল2 :=যোগফল2 + সংখ্যা[i − k]
-
cnt :=cnt + 1
-
avg :=গড় সর্বোচ্চ এবং (sum1 /(cnt + k))
-
যদি sum2 / cnt <=mid, তারপর
-
যোগফল1 :=যোগফল1 − যোগফল2
-
cnt :=0, যোগফল2 :=0
-
-
avg :=গড় সর্বোচ্চ এবং (sum1 /(cnt + k))
-
-
great_avg :=বৃহত্তম_avg এবং avg
এর সর্বোচ্চ -
যদি avg> mid, তারপর
-
বাম :=মধ্য + 1
-
-
অন্যথায়,
-
ডান:=মধ্য − 1
-
-
-
সবচেয়ে বড়_এভিজি
ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution: def solve(self, nums, k): left, right = min(nums), max(nums) s = sum(nums[:k]) largest_avg = s / k while left <= right: mid = (left + right) // 2 sum1 = s avg = s / k sum2 = 0 cnt = 0 for i in range(k, len(nums)): sum1 += nums[i] sum2 += nums[i − k] cnt += 1 avg = max(avg, sum1 / (cnt + k)) if sum2 / cnt <= mid: sum1 −= sum2 cnt = 0 sum2 = 0 avg = max(avg, sum1 / (cnt + k)) largest_avg = max(largest_avg, avg) if avg > mid: left = mid + 1 else: right = mid − 1 return largest_avg ob = Solution() nums = [2, 10, −50, 4, 6, 6] k = 3 print(ob.solve(nums, k))
ইনপুট
[2, 10, −50, 4, 6, 6], k = 3
আউটপুট
5.333333333333333
