第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全，請及時綁定郵箱和手機(jī)立即綁定
已解決430363個問題，去搜搜看，總會有你想問的

使用多個指針作為解決方案的 averagePair 問題

使用多個指針作為解決方案的 averagePair 問題

qq_笑_17 2023-05-25 16:58:09
我正在嘗試解決以下問題：到目前為止我想出了什么：function averagePair(arr,tar){    if (arr.length < 2){        return false    }    let x = 0    for (var y = 1; y < arr.length; y++){        if ((arr[x] + arr[y]) / 2 == tar){            return true        }        else {            x++;        }    }    return false}我知道這個解決方案不正確，有人可以解釋為什么嗎？它適用于某些情況但不是全部
查看完整描述

2 回答

?
烙印99

TA貢獻(xiàn)1829條經(jīng)驗(yàn) 獲得超13個贊

有一個解決方案具有O(1)額外的空間復(fù)雜性和O(n)時間復(fù)雜性。


由于數(shù)組已排序，因此有兩個索引是有意義的：一個從數(shù)組的開頭到結(jié)尾（比如y），另一個從數(shù)組的結(jié)尾到開頭（比如x）。


這是代碼：


function averagePair(arr,tar){

    

    // That's now included in for-loop condition

    // if (arr.length < 2) {

    //     return false;

    // }


    let x = arr.length - 1;


    for (var y = 0; y < x; y++) {


        // Division may lose precision, so it's better to compare

        //   arr[x] + arr[y] > 2*tar

        // than

        //   (arr[x] + arr[y]) / 2 > tar


        while (y < x && arr[x] + arr[y] > 2*tar) {

            x--;

        }

        if (x != y && arr[x] + arr[y] == 2*tar) {

            return true;

        }

    }

    return false;

}

這是一種雙指針技術(shù)：我們將減少x直到a[x] + a[y] > 2*tar當(dāng)前循環(huán)迭代，因?yàn)槲覀冃枰业阶罱咏钠ヅ漤?xiàng)。在下一個 for 循環(huán)迭代a[y]大于或等于前一個，因此檢查是否a[z] + a[y] == 2*tar為 any是沒有意義的z > x。我們將這樣做直到索引不相等，這意味著沒有匹配。


查看完整回答
反對 回復(fù) 2023-05-25
?
婷婷同學(xué)_

TA貢獻(xiàn)1844條經(jīng)驗(yàn) 獲得超8個贊

您只比較相鄰的元素，例如[0]vs[1]和[1]vs [2]。您還需要比較[0]vs[2]等等。最簡單的調(diào)整是使用嵌套循環(huán)：


for (let x = 0; x < arr.length; x++) {

  for (let y = 0; y < arr.length; y++) {

    if (x !== y) {

      // test arr[x] against arr[y]

但是使用 Set 來跟蹤到目前為止發(fā)現(xiàn)的內(nèi)容會更優(yōu)雅且計(jì)算復(fù)雜性更低（O(n)而不是）：O(n ^ 2)


const nums = new Set();

for (const num of arr) {

  if (nums.has(tar - num)) {

    return true;

  } else {

    nums.add(num);

  }

}

function averagePair(arr,tar){

  const nums = new Set();

  for (const num of arr) {

    if (nums.has(tar - num)) {

      return true;

    } else {

      nums.add(num);

    }

  }

  return false;

}


console.log(averagePair([-2, 3, 2], 0));

console.log(averagePair([-2, 3, 3], 0));


查看完整回答
反對 回復(fù) 2023-05-25
  • 2 回答
  • 0 關(guān)注
  • 136 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

 幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

 公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號