題目內容
題目頁面: https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/
題目理解
尋找 (P, Q)，其中0 ≤ P < Q < N，為陣列A的切片，N介於2~100000之間，並尋找最小平均切片的起始位置，要注意的是，陣列的內容為-10000~10000
感覺起來就是要先儲存從0~N的加總，然後再來尋找最小平均切片，但是思考起來這樣子複雜度應該也會有O(N**2)，但是先這樣試看看
解題思路
第一次的嘗試
function solution(A) {
var sum = []
var current_sum = 0
sum.push(0)
for(var i=0;i<A.length;i++){
current_sum += A[i];
sum.push(current_sum)
}
var min = Infinity;
var min_start = -1
for(var i = 0;i<A.length;i++){
for(var j = i+1;j<A.length;j++){
var avg = (sum[j+1]-sum[i])/(j+1-i);
if(min > avg) {
min = avg;
min_start = i
}
}
}
return min_start
}
我就知道….60%，timeout errors。複雜度還是太高，現在的解法是很直接的思考平均算法，先嘗試思考看看”平均”有沒有其他可能的算法
本來想嘗試必定包含最小值得所有可能，但是發現有邏輯錯誤，因為一個最小值不代表平均起來就一定最小，因為若該最小值的左右兩邊比較大，旁邊有兩個比較小的值，平均值會比包含最小值的還要小。所以即便是最小的值也不一定在最小平均之內。
//這會有錯誤的結果
function solution(A) {
var sum = []
var current_sum = 0
sum.push(0)
var mustIncludeIndex = -1
var mustIncludeValue = Infinity
for(var i=0;i<A.length;i++){
current_sum += A[i];
sum.push(current_sum)
if(mustIncludeValue > A[i]) {
mustIncludeValue = A[i];
mustIncludeIndex = i
}
}
var min = Infinity;
var min_start = -1
for(var i = 0;i<mustIncludeIndex;i++){
for(var j = i+1;j<A.length;j++){
var avg = (sum[j+1]-sum[i])/(j+1-i);
if(min > avg) {
min = avg;
min_start = i
}
}
}
return min_start
}
萬般無助之下，詢問了ChatGPT，沒想到他都比我聰明(哭)，好吧這就來改寫!!
以下為改寫後的程式碼
function solution(A) {
var sum = []
var current_sum = 0
sum.push(0)
for(var i=0;i<A.length;i++){
current_sum += A[i];
sum.push(current_sum)
}
var min = Infinity;
var min_start = -1
for(var i = 0;i<A.length;i++){
var max_possible = Math.min(A.length, i+3)
for(var j = i+1;j<max_possible;j++){
var avg = (sum[j+1]-sum[i])/(j+1-i);
if(min > avg) {
min = avg;
min_start = i
}
}
}
return min_start
}
好，100%!謝謝ChatGPT大神!!!
