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中的地圖和匹配範圍

回答

相關問題