【leetcode17-----子数组最大平均数】_平均数为k的最长连续子数组-程序员宅基地

技术标签: 算法  leetcode  力扣算法  职场和发展  

1.题目描述

给你一个由 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

2.题目链接

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximum-average-subarray-i

3.思路讲解

笔者最开始解这道题的时候使用的是暴力解法,结果最后超过了时间限度,然后又对算法进行了优化,要找出平均数最大的长度为 k 的连续子数组,那么只需找出总和最大的长度为 k 的连续子数组,首先计算前k个数的和作为初始值,也作为最大值,然后从第k个数开始向后移动,每次移动子数组和的变化是加上当前元素的值,减去当前元素的k个元素之前的值,每次移动子数组就是进去一个数出去一个数。每次移动都比较一下当前总和与最大值的大小,若大于最大值,则最大值就等于当前总和,最后即可找出具有最大总和的长度为 k 的连续子数组,然后除以k,就得到平均数。

4.模板代码

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double ave;
        
        int sum=0;
        //首先计算前k个数的总和作为初始值
        for(int i=0;i<k;i++){
            sum+=nums[i];
        }
        int max=sum;//也作为最大值
        for(int i=k;i<nums.length;i++){
            sum=sum+nums[i]-nums[i-k];//每次移动总和就等于加上当前元素,减去当前元素的k个数之前的元素
            if(sum>max){//与最大值比较,若比最大值大,则最大值等于sum
                max=sum;
            }
        }
        
        ave=1.0*max/k;
        return ave;
    }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_45071131/article/details/127187176

智能推荐

python之09-tuple元组-程序员宅基地

文章浏览阅读254次。详细请参考:https://www.cnblogs.com/Neeo/articles/11212374.html1、元组的基本操作1>创建元组Python中,元组(tuple)用一对小括号()表示,元组内的各元素以逗号分隔。t = ()print(type(t)) # <type 'tuple'>t1 = ('name', )print(t1) ..._tuple元祖for循环取值

c语言程序怎样生产dll文件,关于c语言创建dll文件及dll文件的调用-程序员宅基地

文章浏览阅读860次。关于c语言创建dll文件及dll文件的调用近来又有人在群里问如何用c语言编制dll文件(动态链接库)。原来没有对这个问题太在意过,也没有尝试过任何解决方案,毕竟原来我是用vb的(现在用.net),做个dll只不过是点选一下建立activeX dll工程的图标而已。今天在网上与朋友聊天,看了他指给我的几个几个文件,用MingW将C程序编译成dll文件的例子,我恍然大悟,原来讲C程序编译成dll文件只..._keil c语言 生成dll

【学习笔记】基于遗传算法的BP神经网络优化算法_遗传算法优化 bp 染色体-程序员宅基地

文章浏览阅读6.8k次,点赞11次,收藏111次。一、背景介绍BP神经网络是一类多层的前馈神经网络。它的名字源于在网络训练的过程中,调整网络的权值的算法是误差的反向传播的学习算法,即为BP学习算法。BP神经网络是人工神经网络中应用广泛的算法,但依然存在着一些缺陷,例如学习收敛速度太慢、不能保证收敛到全局最小点、网络结构不易确定等。另外,网络结构、初始连接权值和阈值的选择对网络训练的影响很大,但是又无法准确获得,针对这些特点可以采用遗传算法对神经网络进行优化。二、算法流程创建网络;确定网络的初始权重值和阈值,对其进行编码得到初始种群;while_遗传算法优化 bp 染色体

Redis6 主从复制及哨兵机制_redis 6 哨兵-程序员宅基地

文章浏览阅读316次。Sentinel(哨兵)进程是用于监控Redis集群中Master主服务器工作的状态在Master主服务器发生故障的时候,可以实现Master和Slave服务器的切换,保证系统的高可用(HA)其已经被集成在redis2.6+的版本中,Redis的哨兵模式到了2.8版本之后就稳定了下来。......_redis 6 哨兵

C语言 | 链表的建立和剔除_snode *init()-程序员宅基地

文章浏览阅读363次。单向链表,定义、插入、剔除操作,模块化能直接调用_snode *init()

wide find - replace [转]-程序员宅基地

文章浏览阅读84次。wide find - replace最后更新:2008-09-09, Ver 2.3.4.0909 简介 wfr   - 支持多国语言的字符串批量查找和替换   - 批量字符集编码转换 纯 unicode 规则匹配内核,..._iso-2022-cn-ext

随便推点

Linux系统100条命令:关于Ubuntu和 CentOS 7 相同功能的不同的终端操作命令_ubuntu 命令跟centos-程序员宅基地

文章浏览阅读718次。CentOS 7:ip link set interface_name up 或 ip link set interface_name down。Ubuntu:ifconfig interface_name up 或 ifconfig interface_name down。CentOS 7:编辑 /etc/sysconfig/network-scripts/ifcfg-eth0 文件。Ubuntu:编辑 /etc/network/interfaces 文件。_ubuntu 命令跟centos

windows10下VS2019编译jpegsrc.v9e.tar.gz为lib静态库(已验证)_jpeg library error vs2019-程序员宅基地

文章浏览阅读652次。jpegsr9e windows vs2019生成方法,以及库下载_jpeg library error vs2019

重磅?华为 Mate60/Pro 系列网速实测结果公布,最高 1205.57 Mbps_华为mate60pro+核实网络-程序员宅基地

文章浏览阅读647次。总的来说,华为Mate 60/Pro系列手机的高速网速表现引起了广泛的关注,这也是消费者对该系列手机购买热情高涨的一个重要因素。可以看出,华为Mate 60/Pro系列手机的网速表现非常出色,这也是消费者购买该系列手机的一个重要原因。此前,华为Mate 60 Pro的供应量已经增至1500万至1700万台,而最新消息称,华为Mate 60 Pro和Mate 60 Pro+的出货量甚至已上调至2000万台。目前,在中国市场上,手机竞争愈发激烈,不仅华为Mate 60系列,其他品牌的手机也都受到了高温的迎接。_华为mate60pro+核实网络

access查找出生日期年份_access怎样利用出生日期计算年龄呀!-程序员宅基地

文章浏览阅读7.1k次。公告: 为响应国家净网行动,部分内容已经删除,感谢读者理解。话题:access怎样利用出生日期计算年龄呀!回答:lt;%set rs = server.createobject("adodb.recordset") curid=request("id") sql = "UPDATE pany SET a_num=a_num+1,day_count=day_count+1 WHERE day_lda..._access出生年份表达式

python 内置函数-程序员宅基地

文章浏览阅读75次。Python内置函数(1)——absPython内置函数(2)——divmodPython内置函数(3)——maxPython内置函数(4)——minPython内置函数(5)——powPython内置函数(6)——roundPython内置函数(7)——sumPython内置函数(8)——bool...

希望OL修改服务器经验,希望OL服务端架设技术教程-程序员宅基地

文章浏览阅读2.8k次。经测试自带的MYSQL可能有问题,也可能没问题。如果有问题请下载安装MYSQL5.0然后导入端里面自带的guaiwu.sql希望ol教程=========================================客户端SO3D.exe需要改IP 我这里是在服务器上录像的,我把客户端的SO3D.exe复制到服务端这里了具体更改用UE搜索MessgerIp 在附近找到他的ip 改成你自己的,我这..._希望ol 服务器架设