①英文题目
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