सबलिस्ट का सबसे बड़ा औसत खोजने का कार्यक्रम जिसका आकार कम से कम k पायथन में है

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और दूसरा मान k है, हमें सूची के किसी भी उप-सूची का सबसे बड़ा औसत मान ज्ञात करना है जिसकी लंबाई कम से कम k है।

इसलिए, यदि इनपुट nums =[2, 10, -50, 4, 6, 6] k =3 जैसा है, तो आउटपुट 5.33333333 होगा, क्योंकि सबलिस्ट [4, 6, 6] का औसत मान सबसे बड़ा है

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• बाएँ:=न्यूनतम अंक, दाएँ:=अधिकतम अंक

• s :=सूचकांक 0 से k - 1 तक की सभी संख्याओं का योग

• सबसे बड़ा_औसत :=एस / के

• जबकि बाएं <=दाएं, करें

  • मध्य :=(बाएं + दाएं) का पूर्णांक / 2

  • sum1 :=s, औसत :=s / k, sum2 :=0, cnt :=0

  • k से लेकर अंकों के आकार की श्रेणी में i के लिए, करें

    • sum1 :=sum1 + nums[i]

    • sum2 :=sum2 + nums[i − k]

    • सीएनटी:=सीएनटी + 1

    • औसत :=अधिकतम औसत और (sum1 /(cnt + k))

    • अगर sum2 / cnt <=मध्य, तो

      • sum1 :=sum1 - sum2

      • सीएनटी:=0, योग2:=0

    • औसत :=अधिकतम औसत और (sum1 /(cnt + k))

  • सबसे बड़ा_औसत :=अधिकतम सबसे बड़ा_औसत और औसत

  • अगर औसत> मध्य, तो

    • बायां :=मध्य + 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