首页 > 编程语言 > 详细

[LC]643题 Maximum Average Subarray I(子数组最大平均数 I)

时间:2019-09-15 23:06:44      阅读:104      评论:0      收藏:0      [点我收藏+]

①英文题目

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 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].

②中文题目

给定 n 个整数,找出平均数最大且长度为 k 的连续子数组,并输出该最大平均数。

示例 1:

输入: [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]。

 ③思路

    就是个遍历,去k长度的窗口加和求平均,再滑动这个k长度窗口一步。我自己的思路写出来的代码,太慢了,约1300ms的速度。

④我自己的代码(1300ms级速度)

 1 class Solution {
 2     public double findMaxAverage(int[] nums, int k) {
 3         double sum=0;
 4         double result=0;
 5         double[] aver=new double[nums.length-k+1];
 6         for(int i=0;i<=nums.length-k;i++){
 7              for(int j=i;j<i+k;j++){
 8                   sum+=nums[j];
 9               }        
10              aver[i]=sum/k;
11              sum=0;
12         }
13         Arrays.sort(aver);
14         result =aver[nums.length-k];
15         return result;
16     }
17 }

⑤看了别人的代码之后,照着ta的思路改了之后,速度是4ms

 1 class Solution {
 2     public double findMaxAverage(int[] nums, int k) {
 3         double sum=0;
 4         double result=0;
 5         double[] aver=new double[nums.length-k+1];
 6         double max=-10000;
 7         for(int i=0;i<k;i++){
 8              sum=sum+nums[i];    
 9              result=sum/k;
10         }
11       for(int i=1;i<=nums.length-k;i++){
12           sum=sum-nums[i-1]+nums[i+k-1];
13           if((sum/k)>result)
14               result=sum/k;
15       }
16         
17         return result;
18     }
19 }

   ta比我更先进的思路在于,减少了加法的次数。比如,我每次都要把k窗口里的所有元素加一遍,而它是在上一次k窗口的加和的基础上,减去首部,再在尾部的下一个元素加进来。

   比如

比如 [1,2,3,4,5,6] k=4

temp1 = 1+2+3+4

temp2 = temp1+5-1

 

⑥笔记:1、java里,Math.max只是用于求两个数中的较大值,而不是求一个数组里的最大值。同理min。

              2、Array.sort()函数内部使用的是快排,结果是在原数组的基础上,变成一个升序,比如

                   Array.sort(arr);

                  让arr变成升序了。

[LC]643题 Maximum Average Subarray I(子数组最大平均数 I)

原文:https://www.cnblogs.com/zf007/p/11524234.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!