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

①英文题目

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级速度）

 class Solution {

     public double findMaxAverage(int[] nums, int k) {

         double sum=0;

         double result=0;

         double[] aver=new double[nums.length-k+1];

         for(int i=0;i<=nums.length-k;i++){

              for(int j=i;j<i+k;j++){

                   sum+=nums[j];

               }

              aver[i]=sum/k;

              sum=0;

         }

         Arrays.sort(aver);

         result =aver[nums.length-k];

         return result;

     }

 }

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

 class Solution {

     public double findMaxAverage(int[] nums, int k) {

         double sum=0;

         double result=0;

         double[] aver=new double[nums.length-k+1];

         double max=-10000;

         for(int i=0;i<k;i++){

              sum=sum+nums[i];

              result=sum/k;

         }

       for(int i=1;i<=nums.length-k;i++){

           sum=sum-nums[i-1]+nums[i+k-1];

           if((sum/k)>result)

               result=sum/k;

       }

         return result;

     }

 }

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）

最新文章

热门文章