[问题]请教一道面试题

2016/9/9镜像同步41 回复

一个数组int[] nums，在nums中找到一个连续的子数组，该子数组元素的平均值最大，而且这个子数组的元素不少于4个。当时没想出来，过后思考一下，用start，end两个指针扫一遍是不是可以做出来？

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

flymop机器人#1 · 2016/9/9

是暴力解法二次方的复杂度。排序做法nlogn复杂度。感觉应该有一次复杂度的算法想不出来orz

ffantastic机器人#2 · 2016/9/10

能说说排序做法的思路吗，谢谢【在 flymop 的大作中提到: 】 : 是暴力解法二次方的复杂度。排序做法nlogn复杂度。感觉应该有一次复杂度的算法想不出来orz

tth机器人#3 · 2016/9/10

平均值最大可不可以看成是sum和最大

chihiro2B机器人#4 · 2016/9/10

【在 tth 的大作中提到: 】 : 平均值最大可不可以看成是sum和最大应该不是，因为长度不是固定的

ffantastic机器人#5 · 2016/9/10

转化为最大和子数组问题？但是sum大不代表平均值大吧【在 tth 的大作中提到: 】 : 平均值最大可不可以看成是sum和最大

chihiro2B机器人#6 · 2016/9/10

我觉得扫一遍可以做

guyu111机器人#7 · 2016/9/10

用分治做，复杂度nlgn 发自「贵邮」

kit机器人#8 · 2016/9/10

似乎只需枚举长度为4、5、6、7的区间长度。对于大于等于8的区间，一定可以分成两个长度大于等于4的区间。把两个区间平均值小的舍去就可以得到一个更优的答案，所以最优区间长度小于8。

lz1995机器人#9 · 2016/9/10

好有道理【在 kit 的大作中提到: 】 : 似乎只需枚举长度为4、5、6、7的区间长度。 : 对于大于等于8的区间，一定可以分成两个长度大于等于4的区间。把两个区间平均值小的舍去就可以得到一个更优的答案，所以最优区间长度小于8。发自「贵邮」