在陣列獲取兩個最接近的號碼值

Question

可以說我有數字像這樣的數組：

var a = [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31]; 

它是按升序排序，現在，讓我們說我挑x的值：

var x = 13; 

如何找到最接近x的哪兩個值？

在這種情況下，它將是12和15，但是如何獲得這兩個給定的x，並且如果x低於最低值，那麼只返回最低值，如果它大於最大值，只返回最大值，如果x = 3，那麼只返回一個值，4？

我已經試過這樣：

function getClosest(a, x) { 
    for (var i = 0; i < a.length - 1; i++) { 
     var c1 = a[i], 
      c2 = a[i + 1]; 

     if (x > c1 && x < c2) return [c1, c2]; 
     else if (i == 0) return [c1]; 
     else if (i == a.length - 2) return [c2]; 
    } 
} 

現在，這是我的做法，你將如何解決這個問題/什麼是最有效的解決方案呢？

Answer 1

我相信你的代碼不能按預期工作，因爲如果前兩個元素比你的x小，它將返回第一個元素。你也錯過了x在a中的情況。

如果找到正確的答案，您的代碼具有線性運行時直接返回。

因爲a被排序，您可以通過使用二進制搜索方法優化您的代碼爲O（log n）。

設置[0]和[n]的上限和下限。將x與[n/2]比較。如果x < a [n/2]將您的上界設置爲[n/2]，則將下界設置爲[n/2]。 將x與您的新邊界之間的元素進行比較，並按所述繼續，直到您的上下邊界連續。然後歸還它們。

照顧最小（a）和x> max（a）x <的情況。 分開處理a中的情況x。

Answer 2

您可以使用Array#some和短路。

function closest(value, array) { 
 
    var result = []; 
 
    array.some(function (a) { 
 
     if (a > value) { 
 
      return result.push(a); 
 
     } 
 
     result = [a]; 
 
     return a === value; 
 
    }); 
 
    return result; 
 
} 
 

 
console.log(closest(13, [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31])); 
 
console.log(closest(3, [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31])); 
 
console.log(closest(50, [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31])); 
 
console.log(closest(19, [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31]));

Answer 3

這是略有不同的方法與sort()和slice()

var a = [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31]; 
 

 
function getClosest(num, ar) { 
 
    if (num < ar[0]) { 
 
    return ar[0]; 
 
    } else if (num > ar[ar.length - 1]) { 
 
    return ar[ar.length - 1]; 
 
    } else { 
 
    return ar.sort((a, b) => Math.abs(a - num) - Math.abs(b - num)).slice(0, 2); 
 
    } 
 
} 
 

 
console.log(getClosest(11, a))

Answer 4

這裏是快速的解決方案，也包括最高和最低界限：

var a = [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31]; 

function getClosest(a, x) { 
    var min = Math.min.apply(null, a), max = Math.max.apply(null, a), i, len; 

    if (x < min) { // if x is lower than the lowest value 
     return min; 
    } else if (x > max) { // if x is greater than the 'greatest' value 
     return max; 
    } 
    a.sort(); 
    for (i = 0, len = a.length; i < len; i++) { 
     if (x > a[i] && x < a[i + 1]) { 
      return [a[i], a[i + 1]]; 
     } 
    } 
} 

console.log(getClosest(a, 13)); // [12, 15] 
console.log(getClosest(a, 3)); // 4 
console.log(getClosest(a, 33)); // 31 
console.log(getClosest(a, 25)); // [23, 27] 

Answer 5

查找數組是否存在數字。如果沒有，push它來陣列。對數組進行排序，並獲取該數字的索引。如果這個數字是第一個（零）入口返回數組的第二個元素（arr [1]）。如果是最後一個，則返回元素。 否則返回左邊和右邊的鄰居。

function closest_two(n, arr) { 
    if (arr.indexOf(n) == -1) { 
     arr.push(n); 
    } 
    arr.sort(function(a,b) { return a-b; }) 
    p = arr.indexOf(n); 
    if (p==0) { return arr[1]; } 
    if (p == (arr.length - 1)) { return arr[p-1]; } 

    return[arr[p-1], arr[p+1]] 
} 

Answer 6

我的方法是：如果x不在a中，則將x推到a然後再度假。然後，讓i = indexOf（x），如果它存在，則返回一個[i-1]，如果存在則返回[i + 1]。 a被克隆，因爲push會修改它。

var a = [4, 5, 7, 9, 12, 15, 18, 19, 20, 23, 27, 31]; 
function neighbors(a,x){ 
b=a.slice(0);//clone a 
if (a.indexOf(x) < 0) {//push x onto a if x not in a 
    b.push(x); 
    b.sort((a,b)=>a-b); //resort 
    } 
var i=b.indexOf(x); 
return [i-1 in b ? b[i-1] : null, i+1 in b ? b[i+1] : null].filter(Number); 
} 

neighbors(a,13);//[12,15] 
neighbors(a,12);//[9,15] 
neighbors(a,5);//[4,7] 
neighbors(a,4);//[5] 
neighbors(a,3);//[4] 
neighbors(a,27);//[23,31] 
neighbors(a,28);//[27,31] 
neighbors(a,31);//[27] 
neighbors(a,32);//[31] 

Answer 7

假設數組已排序，可以使用二分搜索。它只會是O(lg n)，比你的O(n)方法少。

function lowerBound(arr, x, from=0, to=arr.length) { 
    if(from >= to) return to-1; 
    var m = Math.floor((from+to)/2); 
    if(a[m] < x) return lowerBound(arr, x, m+1, to); 
    return lowerBound(arr, x, from, m); 
} 
function upperBound(arr, x, from=0, to=arr.length) { 
    if(from >= to) return to; 
    var m = Math.floor((from+to)/2); 
    if(a[m] > x) return upperBound(arr, x, from, m); 
    return upperBound(arr, x, m+1, to); 
} 
function getClosest(a, x) { 
    var lb = lowerBound(a, x), 
     ub = upperBound(a, x, lb+1), 
     res = []; 
    if(lb >= 0) res.push(a[lb]); 
    if(ub < a.length) res.push(a[ub]); 
    return res; 
}