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

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

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

为了解决这个问题,我们将遵循以下步骤-

  • 左:=最小数字,右:=最大数字

  • s:=从索引0到k − 1的所有数字的总和

  • maximum_avg:= s / k

  • 当左<=右时,执行

    • 右:=中− 1

    • 左:=中+ 1

    • sum1:= sum1 + nums [i]

    • sum2:= sum2 + nums [i-k]

    • cnt:= cnt + 1

    • 平均:=最大平均值和(sum1 /((cnt + k))

    • 如果sum2 / cnt <=中,则

    • 平均:=最大平均值和(sum1 /((cnt + k))

    • sum1:= sum1 − sum2

    • cnt:= 0,sum2:= 0

    • 中:=(左+右)/ 2的整数

    • sum1:= s,平均:= s / k,sum2:= 0,cnt:= 0

    • 对于范围在k到nums的i

    • maximum_avg:= maximum_avg和avg的最大值

    • 如果平均>中间,则

    • 除此以外,

    • 返回maximum_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

    以上是 在Python中寻找大小至少为k的子列表的最大平均值的程序 的全部内容, 来源链接: utcz.com/z/350126.html

    回到顶部