在Python中查找长度至少为k的任何子列表的最大平均值的程序

假设我们有一个名为nums的数字列表和另一个值k，我们必须找到列表的任何子列表的最大平均值，其长度至少为k。

因此，如果输入为nums = [2, 10, -50, 4, 6, 6] k = 3，则输出将是5.33333333，因为子列表[4,6,6]具有最大的平均值

为解决这个问题，我们将按照以下步骤进行 –

left：nums的最小值，right：nums的最大值
s：从索引0到k-1中所有数字的总和
largest_avg：s / k
while left <= right，do
- mid：（left+ right）/ 2的整数
- sum1：s，avg：s / k，sum2：0，cnt：0
- for i in range k to size of nums，do
  - sum1：sum1 + nums [i]
  - sum2：sum2 + nums [i-k]
  - cnt：cnt + 1
  - avg：avg和（sum1 /（cnt + k））的最大值
  - 如果sum2/cnt <= mid，then
  - sum1：sum1-sum2
  - cnt：0，sum2：0
  - avg：avg和（sum1 /（cnt + k））的最大值
- largest_avg：largest_avg和avg的最大值
- 如果avg> mid，then
  - left：mid + 1
- 否则，
  - right：mid – 1
return largest_avg

让我们看看以下实现，以获得更好的理解 –

更多Python相关文章，请阅读：Python 教程

示例

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))