Giả sử chúng ta có một danh sách các số được gọi là num và một giá trị khác k, chúng ta phải tìm giá trị trung bình lớn nhất của bất kỳ danh sách con nào trong danh sách có độ dài ít nhất là k.
Vì vậy, nếu đầu vào là nums =[2, 10, -50, 4, 6, 6] k =3, thì đầu ra sẽ là 5,33333333, vì danh sách con [4, 6, 6] có giá trị trung bình lớn nhất
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
left:=tối thiểu nums, right:=tối đa nums
-
s:=tổng của tất cả các số trong nums từ chỉ số 0 đến k - 1
-
lớn nhất_avg:=s / k
-
trong khi bên trái <=bên phải, thực hiện
-
mid:=integer of (left + right) / 2
-
sum1:=s, avg:=s / k, sum2:=0, cnt:=0
-
đối với tôi trong phạm vi từ k đến kích thước của nums, thực hiện
-
sum1:=sum1 + nums [i]
-
sum2:=sum2 + nums [i - k]
-
cnt:=cnt + 1
-
trung bình:=tối đa trung bình và (sum1 / (cnt + k))
-
nếu sum2 / cnt <=mid, thì
-
sum1:=sum1 - sum2
-
cnt:=0, sum2:=0
-
-
trung bình:=tối đa trung bình và (sum1 / (cnt + k))
-
-
lớn nhất_avg:=tối đa của lớn nhất_avg và trung bình
-
nếu trung bình> trung bình, thì
-
left:=mid + 1
-
-
nếu không,
-
right:=mid - 1
-
-
-
trả về large_avg
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
[2, 10, −50, 4, 6, 6], k = 3
Đầu ra
5.333333333333333