java - findMaxAverage 大数组失败测试用例

Question

问:给定n个整数，找到平均值最大且长度为k的连续子数组，并输出最大平均值。

输入:[1,12,-5,-6,50,3]，k = 4
输出:12.75
例如:maxAvr (12-5-6+50)/4 = 51/4 = 12.75

<小时/>

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double[] f = new double[nums.length];//save the max value f[i] with range k from nums[]
        int length = nums.length;
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        if (length == k) {
            return ((double) sum /  k);
        }
        f[k - 1] = (double)sum; // start at f[k-1]
        for (int i = k - 1; i < length - 1; i++) {
            f[i + 1] = f[i] - nums[i - k + 1] + nums[i + 1]; // with dp to find the maxValue in the range k 
        }
        Arrays.sort(f);
        return (double) f[length - 1] / (double) k;
    }
}

<小时/>

调试

• ✘ 错误答案
• ✘ 测试用例:一个大数组，有 6514 项
• ✘ 118/123 例通过(不适用)
• ✘ 答案:
• ✘ 标准输出:'0.0'

当我调试时，我发现idea.sh无法解决大数组

Answer 1

谢谢我已经解决了，Arrays.sort()花费了很多时间，所以我使用了另一种方法!

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double[] f = new double[nums.length];
        int length = nums.length;
        int sum = 0;
        double pre = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        if (length == k) {
            return ((double) sum /  k);
        }
        f[k - 1] = (double)sum; 
        pre = f[k-1]; // save the max  value
        for (int i = k - 1; i < length -1; i++) {
            f[i + 1] = f[i] - nums[i - k + 1] + nums[i + 1]; 
            if(f[i+1]>pre){
                pre = f[i+1]; // exchange the max value 
            }
        }
        // Arrays.sort(f);   // waste much time!
        return (double) pre / (double) k;
}
}