javascript - javascript中的映射和匹配范围

Question

在 JavaScript 中使用数组映射范围最有效的是什么？

我有这个：

var def = [70,200,1000];

还有一系列可能的数字，比如：

var n = [23,45,74,120,240,800,1204,2000];

现在，如何从中提取n与 中的值匹配的最接近的值def？

在上面的例子中，我会得到[74,240,800]. 我希望我清楚自己...

Answer 1

这是一个尝试。迭代def一次n：

var nIndex = 0,
    nlen = n.length,
    prev,
    next;

for(var i = 0, ilen = def.length; i < ilen && nIndex < nlen; i++) {
    var current = def[i];

    while (n[nIndex] < current && nIndex < nlen - 1) nIndex++;

    next = n[nIndex];
    prev = nIndex == 0 ? next : n[nIndex - 1];

    result[i] = current - prev < next - current ? prev : next;
}
// values in def are larger than the greatest value in n
while (result.length < def.length) result.push(n[nlen-1]);

小提琴

Answer 2

http://jsfiddle.net/8bY2M/

var def = [70,200,1000];
var n = [23,45,74,120,240,800,1204,2000];

var result = [];

for (var i = 0; i < def.length; i++){
    var val = def[i];
    for (var j = 0; j < n.length; j++){
        var nVal = n[j];                
        if (nVal > val){
            var closest = n[j-1] == undefined ? nVal : 
                nVal - val > val - n[j-1] ? n[j-1] : nVal;

            result.push(closest);
            break;
        }    
    }
}

console.log(result); // outputs: [74, 240, 800] 

请注意，如果有两个匹配项，这将使用较大的值。（即如果您尝试匹配 70，并且 n 包含 66 和 74，这将与 74 匹配）

Answer 3

其他解决方案非常简单，但如果您正在寻找效率，最好的办法是对初始列表进行预排序（如果尚未排序），然后执行二进制搜索。这是我的解决方案：

var def = [70,200,1000];
var n = [23,45,74,120,240,800,1204,2000];

var findClosest = function(n, def) {
    var i, result = [];

    n = n.sort(function(a, b) { return a - b; }); //numeric sort


    var closestN = (function(val) {
        return (function search(r) {
            var mid = r.low + (0 | ((r.high - r.low) / 2));

            if(n[mid] === val) { 
                return n[mid];
            }

            if((r.high - r.low) === 1) {
                return n[r[(Math.abs(n[r.low] - val) > Math.abs(n[r.high] - val)) ? "high" : "low"]];
            }

            r[(val < n[mid]) ? "high" : "low"] = mid;

            return search(r);
        }({low : 0, high: (n.length - 1)})); 
    });

    for (i=0; i<def.length; i++) {
        result.push(closestN(def[i]));    
    }

    return result;
};

//The result can be obtained with findClosest(n, def)

请注意，它的可读性不是很高（如果您不熟悉二进制搜索算法），并且如果您正在寻找性能不重要的简单解决方案，线性搜索会产生更易于维护的代码。但是这个解决方案在 O(n log(n)) 时间内运行，而不是像线性搜索那样在 O(n^2) 时间内运行。

你可以在这里看到它的实际效果：

http://jsfiddle.net/naYu6/

请注意，在“平局”的情况下（列表中的两个值与所讨论的值等距，将选择两者中较低的一个）。