使用大数组找到最大平均值测试失败
问：给定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; } } 调试
Answer错误的答案 ✘测试案例：大型数组，包含6514个项目 passed 118/123起案件通过（不适用） ✘答案： ✘标准输出：“ 0.0” 当我调试时，我发现idea.sh无法解决大数组
写回答
-
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; } }
2019-10-09 15:37:02赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
