【LeetCode】数组-1(643)-返回规定长度k的最大子数组的平均数

好久没有刷LeetCode了,准备重拾并坚持下去,每天刷个两小时。今天算是开始的第一天,不过出师不利,在一道很简单的题目上墨迹半天。不过还好,现在踩过的坑,应该都不会白踩,这些可能都是以后程序员路上稳固的基石哦。任何优秀的程序员不都是这样过来的嘛,坚持就好。

注意:大家练习时同样要注意代码的风格,这一点推荐上lintcode测试一下,练习几次风格自然就好了。

下面开始写第一题的解题过程(包括写错的过程)

思路一:累加数组

1. 求出数组的累加数组(循环遍历,每一项等于前一项的和)
2. k个数的和等于 i 位置上的数减去 i - k 位置上的数(对于坐标比较迷糊的同学,推荐你们在稿纸上画画就明白了)。

第一遍错误的代码(黄色标记处错误):

 public class Solution {
public double findMaxAverage(int[] nums, int k) {
if (nums == null || nums.length < 1) {
return -1;
}
int[] ans = new int[nums.length];
double maxSum = 0;
ans[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
ans[i] = nums[i] + nums[i - 1];
}
maxSum = ans[k - 1];
for (int i = k; i < nums.length; i++) {
double curSum = (double)ans[i] - ans[i - k];
if (curSum > maxSum) {
maxSum = curSum;
}else {
continue;
}
}
return maxSum / k;
}
}

nums改成ans就正确了。

时间复杂度:O(n)只是两遍遍历,没有嵌套。

空间复杂度:O(n)申请了一个数组

思路二:滑动窗口

维护一个“和”数组,只有k个元素,从k+1开始,每次右边加一个元素,左边减一个元素。

相比一的好处:不用申请数组了,而且效率也高了,减少了重复计算。

这次终于BugFree了,不容易啊。

 public class Solution {
public double findMaxAverage(int[] nums, int k) {
if (nums.length < 1 || nums == null) {
return -1;
}
int sum = 0;
int max = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];// 先求前k个数的和,之后不断维护这个数组即可。
max = sum;
}
for (int i = k; i < nums.length; i++) {
sum += nums[i] - nums[i - k];
if (sum > max) {
max = sum;
}
}
return max * 1.0 / k;
}
}

时间复杂度:O(n)只是遍历一遍

空间复杂度:O(1)

上一篇:利用KMeans聚类进行航空公司客户价值分析


下一篇:CSS 动画之十-图片+图片信息展示