मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और एक अन्य मान k है, हमें किसी भी सबलिस्ट का सबसे बड़ा औसत मान ज्ञात करना है जिसकी लंबाई कम से कम k है।
इसलिए, यदि इनपुट nums = [2, 10, -50, 4, 6, 6] k = 3 जैसा है, तो आउटपुट 5.33333333 होगा, क्योंकि सबलिस्ट [4, 6, 6] का सबसे बड़ा औसत मान है।
हल करने के चरण
left := nums का न्यूनतम, right := nums का अधिकतम
s := nums में इंडेक्स 0 से k - 1 तक सभी संख्याओं का योग
largest_avg := s / k
जब तक left <= right, करें
mid := (left + right) / 2 का पूर्णांक
sum1 := s, avg := s / k, sum2 := 0, cnt := 0
i के लिए k से nums के आकार तक की रेंज में, करें
sum1 := sum1 + nums[i]
sum2 := sum2 + nums[i - k]
cnt := cnt + 1
avg := avg और (sum1 / (cnt + k)) का अधिकतम
यदि sum2 / cnt <= mid, तो
sum1 := sum1 - sum2
cnt := 0, sum2 := 0
avg := avg और (sum1 / (cnt + k)) का अधिकतम
largest_avg := largest_avg और avg का अधिकतम
यदि avg > mid, तो left := mid + 1
अन्यथा, right := mid - 1
largest_avg लौटाएं
उदाहरण
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
