【leetcode17-----子数组最大平均数】

这篇具有很好参考价值的文章主要介绍了【leetcode17-----子数组最大平均数】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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,就得到平均数。文章来源地址https://www.toymoban.com/news/detail-703357.html

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;
    }
}

到了这里,关于【leetcode17-----子数组最大平均数】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言计算N个数的平均数

    程序如下所示:  #define _CRT_SECURE_NO_WARNINGS #includestdio.h #define N 10//使用define语句将10赋值给符号常量N,(求10个数的平均值)  int main() {     int count;     float sum, average, number;//声明变量,     sum = 0;     count = 1;     while(countN)//while循环语句,用循环语句求和     {     

    2024年02月07日
    浏览(39)
  • 高基数类别特征预处理:平均数编码

    对于一个类别特征,如果这个特征的取值非常多,则称它为高基数(high-cardinality)类别特征。在深度学习场景中,对于类别特征我们一般采用Embedding的方式,通过预训练或直接训练的方式将类别特征值编码成向量。在经典机器学习场景中,对于有序类别特征,我们可以使用

    2024年02月11日
    浏览(44)
  • python计算平均数、中位数及标准差

    哈喽,大家好呀,下面是我整理的python计算平均数、中位数和标准差的方法,咱们一起学习,共同进步! 1.计算平均数 方法① lst=[1,2,3,4,5]                 #首先定义一个列表  avg= sum (lst)/ len (lst)     #使用sum( )函数和len( )函数计算平均值 print(\\\'平均值为:\\\',avg) 方法② impo

    2024年02月17日
    浏览(40)
  • 高基数类别特征预处理:平均数编码 | 京东云技术团队

    对于一个类别特征,如果这个特征的取值非常多,则称它为高基数(high-cardinality)类别特征。在深度学习场景中,对于类别特征我们一般采用Embedding的方式,通过预训练或直接训练的方式将类别特征值编码成向量。在经典机器学习场景中,对于有序类别特征,我们可以使用

    2024年02月10日
    浏览(49)
  • C++编程计算平均数、众数和中位数,可以快速解决计算问题

    说明 求N个整数的平均数,众数和中位数。 小知识: 众数 如有9个数:17 13 17 9 17 17 3 16 17 17出现的次数最多,即为这组数的众数。 此题保证众数是唯一的。 中位数 如有9个数:102 170 96 90 97 106 110 182 100 将这9个数按一定的顺序(从大到小或从小到大)排列后得到: 182 170 110

    2024年02月07日
    浏览(74)
  • 【Python 数据分析】描述性统计:平均数(均值)、方差、标准差、极大值、极小值、中位数、百分位数、用箱型图表示分位数

    前面讲了数据分析中的第一步:数据预处理,下面就是数据分析的其中一个重头戏:描述性统计,具体内容为: 平均数(均值)、方差、标准差、极大值、极小值、中位数、百分位数、用箱型图表示分位数 。 关键方法 含义 .mean() 求均值 .var() 求方差 .std() 求标准差 .max() 求极

    2024年01月21日
    浏览(46)
  • ( 动态规划) 674. 最长连续递增序列 / 718. 最长重复子数组——【Leetcode每日一题】

    难度:简单 给定一个未经排序的整数数组,找到最长且 连续递增的子序列 ,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l r) 确定,如果对于每个 l = i r ,都有 nums[i] nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

    2024年02月05日
    浏览(52)
  • LeetCode | C++ 动态规划——300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

    300题目链接 dp 数组定义 dp[i] 表示 i 之前包括 i 的以 nums[i]结尾 的最长递增子序列的长度 需要包含nums[i]结尾,不然在做递增比较的时候,就没有意义了。 递推公式 位置 i 的最长递增子序列 等于 j 从 0 到 i - 1各个位置的最长递增子序列 + 1 的 最大值 if (nums[i] nums[j]) dp[i] = ma

    2024年02月16日
    浏览(48)
  • 【LeetCode动态规划#14】子序列系列题(最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列)

    力扣题目链接(opens new window) 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 输入:nums = [10,9,2,5,3,7,101,18] 输出

    2024年02月01日
    浏览(56)
  • LeetCode 刷题 数据结构 数组 485 最大连续1的个数

    给定一个二进制数组  nums  , 计算其中最大连续  1  的个数。 示例 1: 示例 2: 提示: 1 = nums.length = 105 nums[i]  不是  0  就是  1.   参看bilibli视频-up主 爱学习的饲养员,讲解的很清晰。 手把手带你刷Leetcode力扣|各个击破数据结构和算法|大厂面试必备技能【已完结】-

    2024年02月15日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包