nums라는 숫자 목록과 다른 값 k가 있다고 가정하고 길이가 k 이상인 목록의 하위 목록에서 가장 큰 평균 값을 찾아야 합니다.
따라서 입력이 nums =[2, 10, -50, 4, 6, 6] k =3과 같으면 하위 목록 [4, 6, 6]이 가장 큰 평균 값을 가지므로 출력은 5.33333333이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
왼쪽 :=최소 숫자, 오른쪽 :=최대 숫자
-
s :=인덱스 0부터 k − 1까지의 모든 숫자의 합
-
가장 큰_avg :=s / k
-
왼쪽 <=오른쪽, 수행
동안-
mid :=(왼쪽 + 오른쪽) / 2의 정수
-
sum1 :=s, avg :=s / k, sum2 :=0, cnt :=0
-
k 범위에서 숫자 크기까지의 i에 대해
-
합계1 :=합계1 + 숫자[i]
-
sum2 :=sum2 + nums[i − k]
-
cnt :=cnt + 1
-
avg :=avg의 최대값 및 (sum1 /(cnt + k))
-
sum2 / cnt <=mid이면
-
합계1 :=합계1 − 합계2
-
cnt :=0, sum2 :=0
-
-
avg :=avg의 최대값 및 (sum1 /(cnt + k))
-
-
maximum_avg :=maximum_avg 및 avg의 최대값
-
평균> 중간인 경우
-
왼쪽 :=중간 + 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