最近更新于 2024-05-05 14:19
题目
给定一个整数数组,找出平均数最大且长度为 k 的子数组,并将最大平均值作为返回结果。
测试条件
gcc 9.4.0 – 64位
-no-pie -std=c17 -Wall -Werror=return-type -Werror=address -Werror=sequence-point -Werror=format-security -Wextra -pedantic -Wimplicit-fallthrough -Wsequence-point -Wswitch-unreachable -Wswitch-enum -Wstringop-truncation -Wbool-compare -Wtautological-compare -Wfloat-equal -Wshadow=global -Wpointer-arith -Wpointer-compare -Wcast-align -Wcast-qual -Wwrite-strings -Wdangling-else -Wlogical-op -Wconversion -g -O0 -lm
分析
这个题目可以考虑使用滑动窗口思想来解答,首先先计算出前 k 个数组之和并记录,然后下一轮在前一轮之和的基础上减去第 1 个数组值,并加上第 k+1 个数组值,并比较与上一轮 k 个之和,如果更大就保存并替换原来记录的最大值,又是一轮,在 k 个数之和基础上减去第 2 个数组值,再加上第 k+2 个数组值,再比较和上一轮的最大值…… 也就是每一轮减去上一轮的 k 个数之和中的第一个并加上下一个,也就实现了依次计算连续的四个最大值之和,返回值算平均值即可,注意传入的数组元素为整数,计算平均数应该转为浮点数进行计算。
如果按照暴力枚举的思想,第一轮计算第 1、2…k 个数组值相加,第 2 轮计算第 2、3…k+1 个数组相加,第 3 轮计算 3、4…k+2 个数组相加……。每一轮都是 k 个数相加,相比与滑动窗口每一轮只减去第一个并加上下一个而言计算量更大,效率更低。
代码实现
float solution(int *nums, size_t size, size_t k) { int sum = 0; for (size_t i = 0; i < k; ++i) // 前 k 个数之和 { sum += nums[i]; } int max = 0; for (size_t i = k; i < size; ++i) // 从第 k+1 个元素开始往后滑动 { if (sum > max) { max = sum; } sum = sum - nums[i-k] + nums[i]; // 减去上一轮的第一个,加上后一位 } return (float)max / (float)k; }
![](https://blog.iyatt.com/wp-content/uploads/2022/02/2022-02-06-14-36-03-的屏幕截图-1024x712.png)
子数组最大平均数