Pythonでサイズがk以上のサブリストの最大平均を見つけるプログラム

numsと呼ばれる数値のリストと別の値kがあるとすると、長さが少なくともkであるリストのサブリストの最大平均値を見つける必要があります。

したがって、入力がnums =[2、10、-50、4、6、6] k =3の場合、サブリスト[4、6、6]の平均値が最大になるため、出力は5.33333333になります。

これを解決するには、次の手順に従います-

• 左：=最小数、右：=最大数

• s：=インデックス0からk −1までのnumsのすべての数値の合計

• maximum_avg：=s / k

• 左<=右、実行

  • mid：=（左+右）の整数/ 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））

  • maximum_avg：=maximum_avgとavgの最大値

  • avg> midの場合、

    • 左：=半ば+ 1

  • それ以外の場合

    • 右：=mid − 1

• 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