j

jaryue

V1

2023/04/28阅读:38主题:默认主题

leetcode 643. 子数组最大平均数 I

leetcode 643. 子数组最大平均数 I


题目描述

  1. 子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组,并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例 1:

输入:nums = [1,12,-5,-6,50,3], k = 4 输出:12.75 解释:最大平均数 (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(数量)

  • 计算最大和值
  1. 计算前k个数的和值
  2. 指针向后移动,加上后一位的值再减去第一个的值计算出这个区间的和值,再与最大的和值进行比较,
  3. 大于则将该值作为最大值
  4. 一直循环遍历整个数组找出最大是k值区间
  • 除以k求得结果
  • 时间复杂度(O(n))
  • 空间复杂度(O(1))

执行结果

法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)
}

执行结果: 通过 显示详情 查看示例代码 添加备注

执行用时: 140 ms , 在所有 Go 提交中击败了 81.28% 的用户 内存消耗: 8.2 MB , 在所有 Go 提交中击败了 52.97% 的用户 通过测试用例: 127 / 127 炫耀一下:

法2


法3


分类:

后端

标签:

后端

作者介绍

j
jaryue
V1