Prefix Sums – MinAvgTwoSlice解題紀錄

題目內容

題目頁面: 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大神!!!