这是悦乐书的第 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 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/f4f94d8c2182