leetcode-643-Maximum Average Subarray I

题目描述:

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

  1. 1 <= k <= n <= 30,000.
  2. Elements of the given array will be in the range [-10,000, 10,000].

要完成的函数:

double findMaxAverage(vector<int>& nums, int k)

说明:

这道题目十分容易,给定一个vector和数值k,我们可以得到长度为k的多个连续的子vector,要求返回这些子vector中的最大平均值。

我们可以遍历一遍vector就得到了结果,存储和的最大值,最后除以k即可得到。

为了降低花费的时间,我们也不需要每次都计算k个元素的和,减去最前面一个和加上新增加的一个即可,类似于滑动窗口。

代码如下:

    double findMaxAverage(vector<int>& nums, int k) 
    {
        int s1=nums.size();
        int sum=0;
        for(int i=0;i<k;i++)
            sum+=nums[i];
        int i=1,max1=sum;
        while(i+k<=s1)
        {
            sum-=nums[i-1];
            sum+=nums[i+k-1];
            max1=max(max1,sum);
            i++;
        }
        return double(max1)/k;
    }

上述代码实测174ms,beats 81.87% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

LeetCode75.颜色分类

 这道题两种做法,一种是用计数排序,因为告诉了你只有3种数字,所以直接创建一个长度为3的数组arr,然后遍历一遍原数组,每出现一次某个数,arr对应位置的值...

672
来自专栏菩提树下的杨过

python高级特性:切片/迭代/列表生成式/生成器

1943
来自专栏机器学习从入门到成神

牛客网刷题汇总(一)附解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

6342
来自专栏一个会写诗的程序员的博客

Sting str = "aaaa" 的形式定义一个字符串最大长度只能有 65534 个。

为什么呢?因为在class文件的规范中, CONSTANT_Utf8_info表中使用一个16位的无符号整数来记录字符串的长度的,最多能表示 65536个字节,...

772
来自专栏测试开发架构之路

C/C++常用头文件及函数汇总

C/C++头文件一览 C #include <assert.h>    //设定插入点 #include <ctype.h>     //字符处理 #inclu...

4345
来自专栏Python小屋

Python科学计算扩展库numpy中的广播运算

首先解答上一个文章Python扩展库numpy中的布尔运算中的问题,该题答案为[111, 33, 2],题中表达式的作用是按列表中元素转换为字符串后的长度降序排...

3018
来自专栏mukekeheart的iOS之旅

No.016 3Sum Closest

16. 3Sum Closest Total Accepted: 86565 Total Submissions: 291260 Difficulty: Med...

2518
来自专栏包子铺里聊IT

关于String Edit Distance问题的总结

包子IT面试培训 助你拿到理想的offer! [例题1] 找到一个字典中与当前输入string的edit distance [1],(edit distance...

3618
来自专栏racaljk

Leetcode 8. String to Integer (atoi) atoi函数实现 (字符串)

这道题的corner cases非常多,请务必确保下面cases都能通过的情况下再提交。

2153
来自专栏逆向技术

逆向知识十一讲,识别函数的调用约定,函数参数,函数返回值.

      逆向知识十一讲,识别函数的调用约定,函数参数,函数返回值. 在反汇编中,我们常常的会看到各种的函数调用,或者通过逆向的手段,单独的使用这个函数,那么...

2539

扫码关注云+社区

领取腾讯云代金券