数组之间的差异

我想找到一个比较两个数组并返回数组元素差异的快速方法。我想出了一些N2，但有更多的循环，有没有更好的方法来做到这一点？数组之间的差异

/** 
* Return the difference of two arrays 
* 
* @param {Array} other, the second array to be compared 
* @param {Funciton} comparison_function, callback function for comparisons 
* @returns {Array} 0 -- indexes of elements only in the first array 
*     1 -- indexes of elements only in the second array 
*/ 
Array.prototype.difference = function(other, comparison_function){ 
    comparison_function = comparison_function || function(a,b){ return a == b;}; 
    var extra = [], 
     matched = [] 
     element_found = false; 
    // fill matched with all values 
    for(var _j = 0; _j < other.length; _j++){matched.push(_j);} 
    for(var _i = 0; _i < this.length; _i++){ 
     element_found = false; 
     for(var _j = 0; _j < other.length; _j++){ 
      if(comparison_function(this[_i], other[_j])){ 
       matched[_j] = undefined; 
       element_found = true; 
       break; 
      } 
     } 
     if(!element_found) extra.push(_i); 
    } 
    return [extra, matched.filter(function(x){ return x !== undefined })]; 
}

来源

2014-06-20 xcorat

这个问题似乎是脱离主题，因为它属于[代码评论]（http://codereview.stackexchange.com）。 – Jon

[JavaScript数组差异]的可能重复（http://stackoverflow.com/a/4026828/341201） – feeela

@feeela我想要的不仅是数组中的额外元素，还有缺少的元素，您引用的问题有只有额外的元素 – xcorat

您正在运行的算法将花费O（n^2）时间。只需对两个数组进行排序，然后以类似于合并的方式找到差异就好多了。这将花费O（n * logn）时间。

来源

2014-06-20 22:56:15 aa333

嗯...但你需要一种方法来排序，不会花更长的时间更短的数组？ – xcorat

你的阵列有多短？如果某个数组太小而无法按快速排序进行排序，则需要更长时间，但在这种情况下，您可以通过直接比较进行排序。您可以根据数组的长度选择排序算法。但仍然排序会胜过O（n^2）。 – aa333

数组之间的差异

回答

相关问题