iT邦幫忙

0

Average pair

兩數相加平均數

  • 必須是被排序好的
  • 應用在找尋有哪些配對符合所要的數值
    接下來讓我們實作吧!!!

迴圈版BigO(n^2)

let array1 = [-11,0,1,2,3,4,5,6,7,8]
let iunputavg = 2

function Average(array, avg){
    let result = [] 
    for(let i = 0; i < array.length -1; i++){
        for(let j = 1; j < array.length -1; j++){ //index0已經當root了 所以j從index1開始即可
            if((array[i] + array[j]) /2 === avg){ //相加/2 === avg
                result.push([array[i],array[j]])
            }
        }   
    }return result
}
console.log(Average(array1, iunputavg))//[ [ 0, 4 ], [ 1, 3 ], [ 2, 2 ], [ 3, 1 ], [ 4, 0 ] ]

Pointer BigO(n)

let array1 = [-11,0,1,2,3,4,5,6,7,8]
let iunputavg = 2

function AveragePointer(array, avg){
    let left = 0
    let right = array.length -1 
    let result = []

    while(array[right] > array[left]){ //當index[i] > index[i-1] = true才執行
        if(((array[right] + array[left]) /2) > avg){
            right --    //若大於目標值 代表右邊範圍過大 right -1
        }else if(((array[right] + array[left]) /2) < avg){
            left ++     //若小於目標值 代表左邊範圍過大 left +1
        }
        else{ //若都符合push result
            result.push([array[right],array[left]])
            right-- //由於已經成功所以要縮小範圍
            left++  //由於已經成功所以要縮小範圍
        }
    }return result
}
console.log(AveragePointer(array1, iunputavg)) //[ [ 4, 0 ], [ 3, 1 ] ]


尚未有邦友留言

立即登入留言