当前位置: 首页 > ops >正文

子数组最大平均数 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

题目解析:

固定长度子数组计算平均值,取最大平均值返回。

解法思路:

暴力解法:计算每个长度为k的子数组的平均数,取最大返回,时间复杂度O(nk)。

固定长度子数组,可以利用定长滑动窗口解法将时间复杂度降到最O(n)。

1.入窗口

2.判断

3.出窗口

4.更新结果

更新结果的代码放在窗口大小达到 k 之后

代码:
class Solution {
public:double findMaxAverage(vector<int>& nums, int k) {int left=0,right=0;double sum=0,ave=INT_MIN;for(;right<nums.size();right++){//入窗口sum+=nums[right];if(right-left+1<k)continue;//判断 + 出窗口if(right-left+1 > k)sum-=nums[left++]; //更新结果ave=max(sum/k,ave); }return ave;}
};

本题细节:

maxAve初始化为INT_MIN,确保可以正确处理所有负数的情况。

http://www.xdnf.cn/news/15250.html

相关文章:

  • Leetcode力扣解题记录--第3题(滑动窗口)
  • WildCard野卡已跑路(包含gpt plus升级方案)
  • 程序改错---字符串
  • 【notes】注意力和KV Cache
  • 检查输入有效性(指针是否为NULL)和检查字符串长度是否为0
  • 阻有形,容无声——STA 签核之RC Corner
  • 加法器学习
  • docker搭建 与镜像加速器
  • scrapy项目开发流程
  • 【数据结构初阶】--单链表(一)
  • C++ Primer(第5版)- Chapter 7. Classes -001
  • AI大模型(七)Langchain核心模块与实战(二)
  • 嵌入式领域编码合集(为什么中文会乱码)
  • (一)一阶数字低通滤波器---原理及其推导
  • web网站无法抓包排查;burp无法抓包情况
  • 实用技巧 Excel 与 XML互转
  • 鸿蒙进程通信的坑之ServiceExtensionAbility
  • 【大模型】深度学习之神经网络
  • Scrapy爬虫中间件核心技术解析:定制化爬虫的神经中枢
  • 9.2 埃尔米特矩阵和酉矩阵
  • 张量拼接操作
  • Git系列--4.Git分支设计规范
  • 深大计算机游戏开发 实验二
  • 8. JVM类装载的执行过程
  • 【读书笔记】《C++ Software Design》第二章:The Art of Building Abstractions
  • c++反射实现
  • Python ExcelWriter详解:从基础到高级的完整指南
  • 网络安全初级--搭建
  • python的婚纱影楼管理系统
  • Redis Geospatial 功能详解及多边形包含判断实现