子数组最大平均数

最近更新于 2022-04-05 12:37

题目

给定一个整数数组，找出平均数最大且长度为 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;
}