西宁软件网站建设,商贸有限公司起名,廊坊视频优化展现,微信商城网站怎么开发文章目录1. 题目2. 解题2.1 暴力超时2.2 二分查找1. 题目
给定一个包含 n 个整数的数组#xff0c;找到最大平均值的连续子序列#xff0c;且长度大于等于 k。并输出这个最大平均值。
样例 1:
输入: [1,12,-5,-6,50,3], k 4
输出: 12.75
解释:
当长度为 5 的时候#xff…
文章目录1. 题目2. 解题2.1 暴力超时2.2 二分查找1. 题目
给定一个包含 n 个整数的数组找到最大平均值的连续子序列且长度大于等于 k。并输出这个最大平均值。
样例 1:
输入: [1,12,-5,-6,50,3], k 4
输出: 12.75
解释:
当长度为 5 的时候最大平均值是 10.8
当长度为 6 的时候最大平均值是 9.16667。
所以返回值是 12.75。注释 :
1 k n 10,000。
数组中的元素范围是 [-10,000, 10,000]。
答案的计算误差小于 10-5 。来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-average-subarray-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 暴力超时
59 / 74 个通过测试用例
class Solution {
public:double findMaxAverage(vectorint nums, int k) {int n nums.size(), i, j, s;double maxAVG INT_MIN, avg;vectorint sum nums;for(i 1; i n; i)sum[i] sum[i-1] nums[i];for(i 0; i n-k; i)for(j ik-1; j n; j){if(i 0)s sum[j];elses sum[j]-sum[i-1];avg s/double(j-i1);if(avg maxAVG)maxAVG avg;}return maxAVG;}
};2.2 二分查找
class Solution {
public:double findMaxAverage(vectorint nums, int k) {double l -10000, r 10000, mid, ans;while(r-l 1e-6){mid (lr)/2.0;if(isok(nums, mid, k)){l mid;ans mid;}elser mid;}return ans;}bool isok(vectorint nums, double avg, int k){ //存在长度至少为k且均值 avg 吗double sum 0, prev 0, minprev 0;//前面最小的前缀和0长度为0时for(int i 0; i k; i)sum nums[i]-avg;//每个数减去平均值求和 0 存在即okif(sum 0) return true;for(int i k; i nums.size(); i){sum nums[i]-avg;prev nums[i-k]-avg;minprev min(minprev, prev);//前面最小的和减去avg后的if(sum-minprev 0)//存在区间使得减去avg后sum0return true;}return false;}
};208 ms 90.3 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
