解
第一步廉沮，萬年不變的查錯凹髓。如果給的array是null或空，那么直接return贫导。
public double maxAverage(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
...
}
思路首先就是因?yàn)橐襰ubarray的最大平均值抛猫，肯定需要知道每一個(gè)subarray的和，所以肯定就得用prefix sum脱盲。先把prefix sum做出來邑滨。Prefix Sum就是把從0到i的和全部存在一個(gè)數(shù)組里日缨，這樣只要用sums[j] - sums[i]就可以知道從i到j的subarray的和钱反。
int n = nums.length;
long[] sums = new long[n + 1];
sums[0] = 0L;
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + nums[i];
}
然后最簡單的做法就是Two Pointer遍歷打擂臺。找出所有大于k的字?jǐn)?shù)組的平均值匣距，然后return面哥。
double maxAvg = Double.NEGATIVE_INFINITY;
for (int i = 0; i < n - k + 1; i++) {
for (int j = i + k; j < n + 1; j++) {
long sum = sums[j] - sums[i];
double avg = ((double) sum) / (j - i);
maxAvg = Math.max(maxAvg, avg);
}
}
return maxAvg;
這個(gè)做法可以過93%的測試。最后一個(gè)測試過不了是因?yàn)橹岛芏嘁愦莚ange很小尚卫，LintCode肯定是希望用二分法解的，所以時(shí)間卡的很小尸红。但是這種方法肯定能解出來吱涉。
完整的code
public class Solution {
/*
* @param nums: an array with positive and negative numbers
* @param k: an integer
* @return: the maximum average
*/
public double maxAverage(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
long[] sums = new long[n + 1];
sums[0] = 0L;
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + nums[i];
}
double maxAvg = Double.NEGATIVE_INFINITY;
for (int i = 0; i < n - k + 1; i++) {
for (int j = i + k; j < n + 1; j++) {
long sum = sums[j] - sums[i];
double avg = ((double) sum) / (j - i);
maxAvg = Math.max(maxAvg, avg);
}
}
return maxAvg;
}
}
解2
二分法的解法，也得用prefix sum外里，但是用法不一樣怎爵。先找出最大值最小值，作為range的start 跟end盅蝗。
double start = (double) nums[0];
double end = (double) nums[0];
for (int i = 0; i < nums.length; i++) {
start = Math.min(start, nums[i]);
end = Math.max(end, nums[i]);
}
然后開始二分鳖链，找出中間數(shù)，看有沒有一個(gè)平均值大于中間數(shù)的字?jǐn)?shù)組存在墩莫，如果有芙委，就把start放在中間，如果沒有狂秦，就把end放在中間灌侣，然后繼續(xù)二分。這里while的條件是end-start >= 1e-6裂问，因?yàn)閐ouble是有小數(shù)點(diǎn)的顶瞳，不能直接對比，所以要對比誤差愕秫。
while (end - start >= 1e-6) {
double mid = start + (end - start) / 2;
if (checkValid(nums, k, mid)) {
start = mid;
} else {
end = mid;
}
}
return end;
怎樣查存不存在這樣的字?jǐn)?shù)組呢慨菱？用prefix sum。但是不是來存和戴甩，而是和減去中間數(shù)符喝。這樣sums[j] - sums[i]就是從i到j的平均值減去中間數(shù)的結(jié)果。舉個(gè)例子甜孤，[1, 2, 3]的sums是[0, 1, 3, 6]协饲，如果中間數(shù)是1畏腕，那么每次計(jì)算下一個(gè)和的時(shí)候，減去中間數(shù)茉稠，sums就變成了[0, 0, 1, 3]描馅。第一個(gè)不需要減，因?yàn)樗韘ize為0的字?jǐn)?shù)組而线，只是用來幫助計(jì)算從第一個(gè)開始字?jǐn)?shù)組的和铭污。這樣，我們就發(fā)現(xiàn)膀篮，如果i是0嘹狞，j是1，那么 sums[j] - sums[i]的結(jié)果就是0誓竿，代表著如果這個(gè)只有1的字?jǐn)?shù)組磅网，平均值不大于我們的中間數(shù)1。而如果j是2筷屡，那么sums[j] - sums[i]的結(jié)果就是1涧偷，大于0，所以這個(gè)包含1毙死，2的字?jǐn)?shù)組燎潮，平均值就大于1。同理规哲，如果中間數(shù)是2跟啤，我們就會發(fā)現(xiàn)sums變成了[0, -1, -1, 0]，所以任何兩個(gè)數(shù)相減大于0唉锌，也就代表著最大的平均值不超過2隅肥。
public boolean checkValid(int[] nums, int k, double mid) {
double minPrev = 0;
double[] sums = new double[nums.length + 1];
sums[0] = 0.0;
for (int i = 0; i < nums.length; i++) {
sums[i + 1] = sums[i] + nums[i] - mid;
if (i + 1 >= k && sums[i + 1] - minPrev > 0) {
return true;
}
if (i + 1 >= k) {
minPrev = Math.min(minPrev, sums[i + 2 - k]);
}
}
return false;
}
具體實(shí)現(xiàn)的方法就是，在算sum的時(shí)候袄简，用前一個(gè)sum加當(dāng)前數(shù)字減去中間數(shù)腥放。如果當(dāng)前個(gè)數(shù)超過k個(gè)了，就找一下k個(gè)之前最小的數(shù)绿语，這樣當(dāng)前sum減去之間最小的數(shù)才會是最大的結(jié)果秃症。如果這個(gè)最大的結(jié)果超過0，代表著最大平均值超過了當(dāng)前的中間數(shù)吕粹，那么返回种柑，然后讓二分法繼續(xù)找下一個(gè)平均數(shù)。如果沒有任何一個(gè)組合超過這個(gè)數(shù)匹耕，那么說明我們的中間數(shù)大于最大平均值聚请，在往小的方向二分。
完整的code
public class Solution {
/*
* @param nums: an array with positive and negative numbers
* @param k: an integer
* @return: the maximum average
*/
public double maxAverage(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
double start = (double) nums[0];
double end = (double) nums[0];
for (int i = 0; i < nums.length; i++) {
start = Math.min(start, nums[i]);
end = Math.max(end, nums[i]);
}
while (end - start >= 1e-6) {
double mid = start + (end - start) / 2;
if (checkValid(nums, k, mid)) {
start = mid;
} else {
end = mid;
}
}
return end;
}
public boolean checkValid(int[] nums, int k, double mid) {
double minPrev = 0;
double[] sums = new double[nums.length + 1];
sums[0] = 0.0;
for (int i = 0; i < nums.length; i++) {
sums[i + 1] = sums[i] + nums[i] - mid;
if (i + 1 >= k && sums[i + 1] - minPrev > 0) {
return true;
}
if (i + 1 >= k) {
minPrev = Math.min(minPrev, sums[i + 2 - k]);
}
}
return false;
}
}
分析
第一個(gè)解法，用prefix sum驶赏，空間是O(n)炸卑，時(shí)間因?yàn)閠wo pointer遍歷，是O((n-k)2)煤傍，也可以是O(n2)盖文。
第二個(gè)解法，用二分法加prefix sum蚯姆，空間還是O(n)五续，時(shí)間的話，二分需要O(log(max-min))蒋失，然后查找valid需要O(n)返帕，所以總共就是O(nlog(max-min))桐玻。
總的來說篙挽，第一個(gè)解法更簡便，也是面試時(shí)跟容易想到的一個(gè)解法镊靴。第二個(gè)實(shí)現(xiàn)更復(fù)雜一點(diǎn)铣卡，prefix sum減去中間數(shù)這種trick你硬要說面試中剛想到的也不大可信。而且log(max-min)純粹取決于數(shù)值的大小偏竟。如果只有兩個(gè)數(shù)煮落，一個(gè)Integer.MIN_VALUE，一個(gè)Integer.MAX_VALUE踊谋，然后k是2蝉仇，那么肯定第一種解法要比第二種解法快得多。第二種解法適合數(shù)很多殖蚕，range很小轿衔，即n很大，max-min很小的案例睦疫。
