C#LeetCode刷题之#643-子数组最大平均数 I( Maximum Average Subarray I)
问题
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3728 访问。
给定 n 个整数,找出平均数最大且长度为 k 的连续子数组,并输出该最大平均数。
输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
注意:
1 <= k <= n <= 30,000。
所给数据范围 [-10,000,10,000]。
Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
Note:
1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].
示例
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3728 访问。
public class Program {
public static void Main(string[] args) {
int[] nums = null;
nums = new int[] { 1, 12, -5, -6, 50, 3 };
var res = FindMaxAverage(nums, 4);
Console.WriteLine(res);
res = FindMaxAverage2(nums, 4);
Console.WriteLine(res);
res = FindMaxAverage3(nums, 4);
Console.WriteLine(res);
Console.ReadKey();
}
private static double FindMaxAverage(int[] nums, int k) {
//暴力解法,此解法LeetCode超时未AC
if(k == 0) return 0;
double sum = 0, max_sum = int.MinValue;
for(int i = 0; i < nums.Length && i + k <= nums.Length; i++) {
sum = 0;
for(int j = i; j < i + k; j++) {
sum += nums[j];
}
max_sum = Math.Max(sum, max_sum);
}
return max_sum / k;
}
private static double FindMaxAverage2(int[] nums, int k) {
//FindMaxAverage的优化解法,不必每次计算k个数字的和
//把k当成一把尺子,从数组左边向右移动,尺子遮挡的部分看成和
//只需用之前存的和减去数组左边移出尺子的值加上数组右边移入尺子的值即为新和
if(k == 0) return 0;
double sum = 0, max_sum = int.MinValue;
//初始状态先计算前k个值的和
for(int i = 0; i < k; i++) {
sum += nums[i];
max_sum = sum;
}
for(int i = 1; i < nums.Length && i + k <= nums.Length; i++) {
//加右减左得到新和
sum += nums[i + k - 1] - nums[i - 1];
max_sum = Math.Max(sum, max_sum);
}
return max_sum / k;
}
private static double FindMaxAverage3(int[] nums, int k) {
//一种常用的数组和的解决方案
int n = nums.Length;
//创建一个新的数组记录前面所有值的和,姑且称为“和数组”
int[] sums = nums.Clone() as int[];
//从第2个(索引为1)数字开始,记录之前所有值的和
for(int i = 1; i < n; ++i) {
sums[i] = sums[i - 1] + nums[i];
}
//定义最大值为前k个数,声明为double是为了最后可以直接返回结果而不用转换
//C#或Java中,整数除以整数得到的结果还是整数,例如10 / 3 = 3,而不是 3.333333
double max = sums[k - 1];
//从k遍历“和数组”到最后,sums[i] - sums[i - k]为中间k个数字的和
for(int i = k; i < n; ++i) {
max = Math.Max(max, (double)sums[i] - sums[i - k]);
}
//返回最大平均数
return max / k;
}
}
以上给出3种算法实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3728 访问。
12.75
12.75
12.75
分析:
显而易见,FindMaxAverage的时间复杂度为: ,FindMaxAverage2和FindMaxAverage3的时间复杂度为: 。
最新文章
- 【原】iOS动态性(五)一种可复用且解耦的用户统计实现(运行时Runtime)
- jQuery入门(4)jQuery中的Ajax应用
- linux 挂载光盘:mount: you must specify the filesystem type
- PAT 1015. 德才论 (25) JAVA
- C++学习笔记(1)——数据类型占空间大小
- ORGANIZATION
- C#:实现快捷键自定义设置
- Android_adb详解
- mac ulimit
- hdu-5586 Sum(dp)
- WPF中Expander控件样式,ListBox的样式(带checkbox)恢复
- [Java] 类的初始化步骤
- 复习篇(一)Activity的生命周期和启动模式
- Binder和SurfaceFlinger以及SystemServer介绍-android学习之旅(79)
- sqlserver数据库NULL类型注意事项
- HTTPD三种工作模型
- 【 Gym - 101138D 】Strange Queries (莫队算法)
- Kali Linux渗透测试实战 2.2 操作系统指纹识别
- Linux服务器部署系列之一—Apache篇(上)
- checkbox数据回显问题