淘客网站代理,前端开发好学吗,手机版企业网站,企业融资难的原因及对策5939. 半径为 k 的子数组平均值
给你一个下标从 0 开始的数组 nums #xff0c;数组中有 n 个整数#xff0c;另给你一个整数 k 。
半径为 k 的子数组平均值 是指#xff1a;nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值#xff0c;即下标在 i …5939. 半径为 k 的子数组平均值
给你一个下标从 0 开始的数组 nums 数组中有 n 个整数另给你一个整数 k 。
半径为 k 的子数组平均值 是指nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值即下标在 i - k 和 i k 范围含 i - k 和 i k内所有元素的平均值。如果在下标 i 前或后不足 k 个元素那么 半径为 k 的子数组平均值 是 -1 。
构建并返回一个长度为 n 的数组 avgs 其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。
x 个元素的 平均值 是 x 个元素相加之和除以 x 此时使用截断式 整数除法 即需要去掉结果的小数部分。
例如四个元素 2、3、1 和 5 的平均值是 (2 3 1 5) / 4 11 / 4 3.75截断后得到 3 。 示例 1输入nums [7,4,3,9,1,8,5,2,6], k 3
输出[-1,-1,-1,5,4,4,-1,-1,-1]
解释
- avg[0]、avg[1] 和 avg[2] 是 -1 因为在这几个下标前的元素数量都不足 k 个。
- 中心为下标 3 且半径为 3 的子数组的元素总和是7 4 3 9 1 8 5 37 。使用截断式 整数除法avg[3] 37 / 7 5 。
- 中心为下标 4 的子数组avg[4] (4 3 9 1 8 5 2) / 7 4 。
- 中心为下标 5 的子数组avg[5] (3 9 1 8 5 2 6) / 7 4 。
- avg[6]、avg[7] 和 avg[8] 是 -1 因为在这几个下标后的元素数量都不足 k 个。示例 2输入nums [100000], k 0
输出[100000]
解释
- 中心为下标 0 且半径 0 的子数组的元素总和是100000 。avg[0] 100000 / 1 100000 。示例 3输入nums [8], k 100000
输出[-1]
解释
- avg[0] 是 -1 因为在下标 0 前后的元素数量均不足 k 。提示
n nums.length1 n 10510^51050 nums[i], k 10510^5105
解题思路
使用前缀和可以快速计算出下标在 i - k 和 i k 范围含 i - k 和 i k内所有元素的总和计算公式为pre[ik]-pre[i-k-1]如果在下标 i 前或后不足 k 个元素则直接跳过该半径为 k 的子数组平均值 的计算。
代码
class Solution {
public:vectorint getAverages(vectorint nums, int k) {int n nums.size(),cnt2*k1;vectorlong long pre(n);vectorint res(n,-1);pre[0]nums[0];for (int i 1; i n; i) {pre[i]pre[i-1]nums[i];}if (2*kn)res[k]pre[2*k]/cnt;for (int i k1; ik n; i) {res[i](pre[ik]-pre[i-k-1])/cnt;}return res;}
};
