LeetCode算法题-Maximum Average Subarray I(Java实现)

时间:2022-04-03 09:28:03

这是悦乐书的第278次更新,第294篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第146题(顺位题号是643)。给定由n个整数组成的数组,找到具有最大平均值的长度为k的连续子数组,并输出最大平均值。例如:

输入:[1,12,-5,-6,50,3],k = 4

输出:12.75

说明:最大平均值为(12-5-6 + 50)/ 4 = 51/4 = 12.75

注意:

  • 1 <= k <= n <= 30,000。

  • 给定数组的元素将在[-10,000,10,000]范围内。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

因为是取连续的子数组,所以不需要对数组进行排序。我们可以先使用一个数组sum,长度与nums一致,将nums中的元素累加的和存起来,然后再去算k个元素之和时,使用sum中的元素做减法,找出其中的最大值,最后算出平均数即可。

public double findMaxAverage(int[] nums, int k) {
// 存放数组元素之和
int[] sum = new int[nums.length];
// 第一位就是数组的第一个元素
sum[0] = nums[0];
for (int i=1; i<nums.length; i++) {
// 从第二位开始,前i个元素之和为sum中的前一个元素与数组的当前元素
sum[i] = sum[i-1] + nums[i];
}
// 第k-1位,就是nums中0到k位元素之和
double result = sum[k-1]*1.0/k;
for (int i=k; i<nums.length; i++) {
// 计算平均值,找出最大值
result = Math.max(result, (sum[i]-sum[i-k])*1.0/k);
}
return result;
}

03 第二种解法

针对上面第一种解法,我们其实也没必要把每组元素的和存起来,只需要存一组k个元素之和即可。然后再计算其他组k个元素时,去掉前面k个元素的头部元素,并且在尾部加上新的元素,就变成了新的一组k个元素之和,就像滑动的窗户一样,窗口大小不变,首尾元素做更新。

public double findMaxAverage(int[] nums, int k) {
double sum = 0;
// 先求出前k个元素之和
for (int i=0; i<k; i++) {
sum += nums[i];
}
// 将最开始的k歌元素之和赋值给result
double result = sum;
for (int i=k; i<nums.length; i++) {
// 减去sum的左边元素,加上右边元素,变成1到k+1位元素之和
sum += nums[i]-nums[i-k];
// 比较大小,取最大
result = Math.max(result, sum);
}
return result/k;
}

04 小结

算法专题目前已日更超过四个月,算法题文章146+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

LeetCode算法题-Maximum Average Subarray I(Java实现)的更多相关文章

  1. LeetCode算法题-Maximum Product of Three Numbers(Java实现)

    这是悦乐书的第275次更新,第291篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第143题(顺位题号是628).给定一个整数数组,从其中找出三个数,使得乘积最大.例如: ...

  2. LeetCode算法题-Maximum Depth of N-ary Tree(Java实现)

    这是悦乐书的第261次更新,第274篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第128题(顺位题号是559).给定n-ary树,找到它的最大深度.最大深度是从根节点到 ...

  3. 【算法】LeetCode算法题-Maximum Subarray

    这是悦乐书的第154次更新,第156篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第13题(顺位题号是53).给定一个整数数组nums,找出一个最大和,此和是由数组中索引 ...

  4. LeetCode算法题-Path Sum III(Java实现)

    这是悦乐书的第227次更新 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第94题(顺位题号是437).您将获得一个二叉树,其中每个节点都包含一个整数值.找到与给定值相加的路径数 ...

  5. LeetCode算法题-Subdomain Visit Count(Java实现)

    这是悦乐书的第320次更新,第341篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第189题(顺位题号是811).像"discuss.leetcode.com& ...

  6. LeetCode算法题-Letter Case Permutation(Java实现)

    这是悦乐书的第315次更新,第336篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第184题(顺位题号是784).给定一个字符串S,将每个字母单独转换为小写或大写以创建另 ...

  7. LeetCode算法题-Jewels and Stones(Java实现)

    这是悦乐书的第313次更新,第334篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第182题(顺位题号是771).字符串J代表珠宝,S代表你拥有的石头.S中的每个字符都是 ...

  8. LeetCode算法题-Reach a Number(Java实现)

    这是悦乐书的第310次更新,第331篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第179题(顺位题号是754).你站在无限数字线的0号位置.在目的地有个target.在 ...

  9. LeetCode算法题-Shortest Completing Word(Java实现)

    这是悦乐书的第309次更新,第330篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第178题(顺位题号是748).从给定的字典单词中查找最小长度单词,其中包含字符串lic ...

随机推荐

  1. Apple WatchKit 初探

    首先新建一个普通project即可. 然后添加WatchKit, file->new->target 直接NEXT后就能见到APPLE WATCH的编辑界面了. 因为apple watch ...

  2. delphi xe5 android sample 中的 SimpleList 是怎样绑定的

    C:\Users\Public\Documents\RAD Studio\12.0\Samples\FireMonkeyMobile 例子中的绑定方式如下图: 1.拖拽一个listview到界面上,然 ...

  3. Scala学习笔记(二)表达式和函数

    笔记的整理主要针对Scala对比Java的新特性:   1.if表达式 if表达式是有结果返回的. val a= if (5>2) "你好" else 1 a的值为if表达式 ...

  4. hysdk代码解析

    navigator 1. navigator.userAgent 浏览器的用户代理字符串 2. navigator.platform 浏览器所在的系统平台 window 1. window.devic ...

  5. PHP的抽象类和接口

    抽象类与接口相似,都是一种比较特殊的类.抽象类是一种特殊的类,而接口也是一种特殊的抽象类.它们通常配合面向对象的多态性一起使用.虽然声明和使用都比较容易,但它们的作用在理解上会困难一点. ①抽象类 在 ...

  6. margin四个属性的顺序

    margin-top ,margin-right ,margin-bottom ,margin-left .方向为 上右下左,顺时针方向, 值可以是: 百分比(基于父对象总高度或宽度的百分比) 长度值 ...

  7. USACO 1&period;4 ariprog 解题报告

    这是继虫洞之后又让我为难的一个 剪枝题目,无论如何,做的再快,也只能过6个点,最后三个点也TLE.后来参考了一下标答,大概思路是这样的. 朴素算法就不多说了,枚举a,b然后判断就行,网上说这样优化到位 ...

  8. hdu 4741 Save Labman No&period;004(2013杭州网络赛)

    http://blog.sina.com.cn/s/blog_a401a1ea0101ij9z.html 空间两直线上最近点对. 这个博客上给出了很好的点法式公式了...其实没有那么多的tricky. ...

  9. 读书笔记 effective c&plus;&plus; Item 5 了解c&plus;&plus;默认生成并调用的函数

    1 编译器会默认生成哪些函数  什么时候空类不再是一个空类?答案是用c++处理的空类.如果你自己不声明,编译器会为你声明它们自己版本的拷贝构造函数,拷贝赋值运算符和析构函数,如果你一个构造函数都没有声 ...

  10. 功能强大的js数组方法:reduce

    arr.reduce()方法接受一个函数作为累加器,数组中的每个值从左到右开始缩减,最终为一个值. reduce接受的参数主要有callback(回调函数)和可选参数initvalue(作为第一次调用 ...