Python程序：查找子列表中大小至少为k的最大平均值

假设我们有一个名为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

  • 对于范围k到nums大小的i，执行以下操作：

    • 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

Arnab Chakraborty

更新于：2020-12-26

246 次浏览

开始您的职业生涯

完成课程获得认证

开始学习