这是悦乐书的第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实现)的更多相关文章
-
LeetCode算法题-Maximum Product of Three Numbers(Java实现)
这是悦乐书的第275次更新,第291篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第143题(顺位题号是628).给定一个整数数组,从其中找出三个数,使得乘积最大.例如: ...
-
LeetCode算法题-Maximum Depth of N-ary Tree(Java实现)
这是悦乐书的第261次更新,第274篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第128题(顺位题号是559).给定n-ary树,找到它的最大深度.最大深度是从根节点到 ...
-
【算法】LeetCode算法题-Maximum Subarray
这是悦乐书的第154次更新,第156篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第13题(顺位题号是53).给定一个整数数组nums,找出一个最大和,此和是由数组中索引 ...
-
LeetCode算法题-Path Sum III(Java实现)
这是悦乐书的第227次更新 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第94题(顺位题号是437).您将获得一个二叉树,其中每个节点都包含一个整数值.找到与给定值相加的路径数 ...
-
LeetCode算法题-Subdomain Visit Count(Java实现)
这是悦乐书的第320次更新,第341篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第189题(顺位题号是811).像"discuss.leetcode.com& ...
-
LeetCode算法题-Letter Case Permutation(Java实现)
这是悦乐书的第315次更新,第336篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第184题(顺位题号是784).给定一个字符串S,将每个字母单独转换为小写或大写以创建另 ...
-
LeetCode算法题-Jewels and Stones(Java实现)
这是悦乐书的第313次更新,第334篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第182题(顺位题号是771).字符串J代表珠宝,S代表你拥有的石头.S中的每个字符都是 ...
-
LeetCode算法题-Reach a Number(Java实现)
这是悦乐书的第310次更新,第331篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第179题(顺位题号是754).你站在无限数字线的0号位置.在目的地有个target.在 ...
-
LeetCode算法题-Shortest Completing Word(Java实现)
这是悦乐书的第309次更新,第330篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第178题(顺位题号是748).从给定的字典单词中查找最小长度单词,其中包含字符串lic ...
随机推荐
-
Apple WatchKit 初探
首先新建一个普通project即可. 然后添加WatchKit, file->new->target 直接NEXT后就能见到APPLE WATCH的编辑界面了. 因为apple watch ...
-
delphi xe5 android sample 中的 SimpleList 是怎样绑定的
C:\Users\Public\Documents\RAD Studio\12.0\Samples\FireMonkeyMobile 例子中的绑定方式如下图: 1.拖拽一个listview到界面上,然 ...
-
Scala学习笔记(二)表达式和函数
笔记的整理主要针对Scala对比Java的新特性: 1.if表达式 if表达式是有结果返回的. val a= if (5>2) "你好" else 1 a的值为if表达式 ...
-
hysdk代码解析
navigator 1. navigator.userAgent 浏览器的用户代理字符串 2. navigator.platform 浏览器所在的系统平台 window 1. window.devic ...
-
PHP的抽象类和接口
抽象类与接口相似,都是一种比较特殊的类.抽象类是一种特殊的类,而接口也是一种特殊的抽象类.它们通常配合面向对象的多态性一起使用.虽然声明和使用都比较容易,但它们的作用在理解上会困难一点. ①抽象类 在 ...
-
margin四个属性的顺序
margin-top ,margin-right ,margin-bottom ,margin-left .方向为 上右下左,顺时针方向, 值可以是: 百分比(基于父对象总高度或宽度的百分比) 长度值 ...
-
USACO 1.4 ariprog 解题报告
这是继虫洞之后又让我为难的一个 剪枝题目,无论如何,做的再快,也只能过6个点,最后三个点也TLE.后来参考了一下标答,大概思路是这样的. 朴素算法就不多说了,枚举a,b然后判断就行,网上说这样优化到位 ...
-
hdu 4741 Save Labman No.004(2013杭州网络赛)
http://blog.sina.com.cn/s/blog_a401a1ea0101ij9z.html 空间两直线上最近点对. 这个博客上给出了很好的点法式公式了...其实没有那么多的tricky. ...
-
读书笔记 effective c++ Item 5 了解c++默认生成并调用的函数
1 编译器会默认生成哪些函数 什么时候空类不再是一个空类?答案是用c++处理的空类.如果你自己不声明,编译器会为你声明它们自己版本的拷贝构造函数,拷贝赋值运算符和析构函数,如果你一个构造函数都没有声 ...
-
功能强大的js数组方法:reduce
arr.reduce()方法接受一个函数作为累加器,数组中的每个值从左到右开始缩减,最终为一个值. reduce接受的参数主要有callback(回调函数)和可选参数initvalue(作为第一次调用 ...