- 題目描述
- 解題思路
- 執(zhí)行結(jié)果
題目描述
-
子數(shù)組最大平均數(shù) I
給你一個由 n 個元素組成的整數(shù)數(shù)組 nums 和一個整數(shù) k 。
請你找出平均數(shù)最大且 長度為 k 的連續(xù)子數(shù)組，并輸出該最大平均數(shù)。
任何誤差小于 10-5 的答案都將被視為正確答案。
示例 1：
輸入：nums = [1,12,-5,-6,50,3], k = 4 輸出：12.75 解釋：最大平均數(shù) (12-5-6+50)/4 = 51/4 = 12.75 示例 2：
輸入：nums = [5], k = 1 輸出：5.00000
提示：
n == nums.length 1 <= k <= n <= 105 -104 <= nums[i] <= 104
解題思路
法1
方法1:滑窗
我們需要得到最大的和值然后再除以k(數(shù)量)
-
計(jì)算最大和值
-
計(jì)算前k個數(shù)的和值 -
指針向后移動,加上后一位的值再減去第一個的值計(jì)算出這個區(qū)間的和值,再與最大的和值進(jìn)行比較, -
大于則將該值作為最大值 -
一直循環(huán)遍歷整個數(shù)組找出最大是k值區(qū)間
-
除以k求得結(jié)果 -
時間復(fù)雜度(O(n)) -
空間復(fù)雜度(O(1))
執(zhí)行結(jié)果
法1
func?findMaxAverage(nums?[]int,?k?int)?float64?{
?t?:=?0
?for?i?:=?0;?i?<?k;?i++?{
??t?+=?nums[i]
?}
?r?:=?t
?for?i?:=?k;?i?<?len(nums);?i++?{
??t?=?t?-?nums[i-k]?+?nums[i]
??if?t?>?r?{
???r?=?t
??}
?}
?return?float64(r)?/?float64(k)
}
執(zhí)行結(jié)果： 通過 顯示詳情 查看示例代碼 添加備注
執(zhí)行用時： 140 ms , 在所有 Go 提交中擊敗了 81.28% 的用戶 內(nèi)存消耗： 8.2 MB , 在所有 Go 提交中擊敗了 52.97% 的用戶 通過測試用例： 127 / 127 炫耀一下:文章來源：http://www.zghlxwxcb.cn/news/detail-430979.html
法2
法3
本文由 mdnice 多平臺發(fā)布文章來源地址http://www.zghlxwxcb.cn/news/detail-430979.html
到了這里，關(guān)于leetcode 643. 子數(shù)組最大平均數(shù) I的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
