資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究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
更新於：2020-12-26
246 次瀏覽
廣告