給定 asorted array和 a number x，在該陣列中找到一個總和最接近 x" 的對。我們如何以O(n)時間復雜度實作這一點？
例子：
fn([10,22,28,29,30,40], 54) // => [22, 30]
fn([1,3,4,7,10], 15) // => [4, 10]
fn([5], 7) // => []
fn([], 7) // => []
uj5u.com熱心網友回復：
基本思想非常簡單。為了從一個非常安全的位置開始，我們將首先嘗試最遠的數字。
1 2 3 4 5
^ ^
l r
現在我們有不同的情況。讓我們成為兩個 num 之和與給定數字之間的差是d
起初我們會允許任何d. 設定一個非常大的數字。
那么如果總和a[l] a[r] < x那么嘗試增加呢？因此，向已排序（升序陣列）的右側移動是合乎邏輯的l
否則，如果是a[l] a[r] > x，則r--減少總和或向左移動。
如果你想知道我為什么要介紹d，也許想一想。但是是的，它只是為了存盤差異。所以它將是的絕對值。a[l] a[r]-x
更準確地說，您只需要運行它直到擁有l<r.
uj5u.com熱心網友回復：
我用javascript代碼解決了它：
function fn(arr, x) {
let res = [];
if (arr.length < 2) return res;
let i = 0,
j = arr.length - 1,
t = Math.abs(arr[i] arr[j] - x);
while (i < j) {
let s = arr[i] arr[j];
if (s === t) {
res = [arr[i], arr[j]];
break;
}
if (s < x) {
i ;
if (Math.abs(arr[i] arr[j] - x) < t) {
t = Math.abs(arr[i] arr[j] - x);
res = [arr[i], arr[j]];
}
}
if (s > x) {
j--;
if (Math.abs(arr[i] arr[j] - x) < t) {
t = Math.abs(arr[i] arr[j] - x);
res = [arr[i], arr[j]];
}
}
}
return res;
}
console.log(fn([10, 22, 28, 29, 30, 40], 54));
console.log(fn([1, 3, 4, 7, 10], 15));
console.log(fn([5], 7));
console.log(fn([], 7));轉載請註明出處，本文鏈接：https://www.uj5u.com/net/469005.html
標籤：javascript 算法 时间复杂度
上一篇：無法在函式中設定狀態