leetcode 2090. 半径为 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$ 的子数组平均值 。
输入:nums = [7,4,3,9,1,8,5,2,6], k = 3
输出:[-1,-1,-1,5,4,4,-1,-1,-1]
来源:leetcode 2090. 半径为 k 的子数组平均值

二、解题报告

1、思路分析

滑动窗口:以i为中心,k为半径的窗口,滑动即是减去前边的数,加上后边的数。

2、代码详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* getAverages(int* nums, int numsSize, int k, int* returnSize){
int *ret=(int *)malloc(sizeof(int)*numsSize);
int l,r;
long long sum[100005],div=2*k+1;

*returnSize=numsSize;
for(int i=0;i<numsSize;i++){
ret[i]=-1;
}
for(int i=k;i<numsSize-k;i++){
if(i==k){
sum[i]=0;
for(int j=0;j<div;j++){
sum[i]+=nums[j];
}//创建窗口
}else{
sum[i]=sum[i-1]-nums[i-k-1]+nums[i+k];
}//窗口滑动
}
for(int i=k;i<numsSize-k;i++){
ret[i]=sum[i]/div;
}
return ret;
}

借鉴:英雄哪里出来

打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2021-2023 lucky_dog
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信