javascript中的地图和匹配范围

在JavaScript中使用数组映射范围最有效？javascript中的地图和匹配范围

我有这样的：

var def = [70,200,1000];

和可能的数字阵列，说：

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

现在，我怎么能提取n该值从def匹配最接近的值？

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

来源

2012-09-05 David

如果对'n'进行排序，则需要对'def'中的每个条目执行二进制搜索，并在最后一次访问时停止，如果不是实际目标。如果没有重复的选择，则从'n'删除条目。这将是'o（#def。log #n）'，如果两者都是通过'n'进行排序的，你可以使它成为'o（#n）'，但如果'def'很小，那么会更糟糕， 'n'高。 – Orbling

如果我们可以假设'n'是一个有序数组，那么逻辑就是这样的：'遍历n直到找到大于这个值。将该值与前一个索引的值进行比较，以确定哪个更接近此值。' – Shmiddty

只是一个想法：如果'def'被排序，那么我们是否真的需要每次循环遍历'n'？ – David

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匹配）

来源

2012-09-05 19:55:15 Shmiddty

这里是一个尝试。遍历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]);

fiddle

来源

2012-09-05 19:56:01 devundef

不错，但是可以用易读的变量得到它，所以我可以遵循吗？它现在看起来有点像汇编器了......另外，小提琴链接是空的。 – David

我觉得现在好多了... – devundef

其他的解决方案是非常简单的，但如果你正在寻找的效率，最好的办法是预先排序的初始列表（如果它不是已经排序），然后执行二分查找。这里是我的解决方案：

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/

注意，在“领带”（即列表中的两个值是从有问题的值等距离，的较低的情况下，两个将被选中）。

来源

2012-09-05 20:33:30 Pete

javascript中的地图和匹配范围

回答

相关问题