首頁猿問使用多個指針作為解決方案的...

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

JavaScript

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貢獻1829條經驗獲得超13個贊

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

由于數組已排序，因此有兩個索引是有意義的：一個從數組的開頭到結尾（比如y），另一個從數組的結尾到開頭（比如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;

}

這是一種雙指針技術：我們將減少x直到a[x] + a[y] > 2*tar當前循環迭代，因為我們需要找到最接近的匹配項。在下一個 for 循環迭代a[y]大于或等于前一個，因此檢查是否a[z] + a[y] == 2*tar為 any是沒有意義的z > x。我們將這樣做直到索引不相等，這意味著沒有匹配。

反對回復 2023-05-25

婷婷同學_

TA貢獻1844條經驗獲得超8個贊

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

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 來跟蹤到目前為止發現的內容會更優雅且計算復雜性更低（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));

反對回復 2023-05-25

2 回答
0 關注
129 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

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

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

2 回答

添加回答