取数组之间的差值

Taking difference between arrays

本文关键字:之间 数组      更新时间:2023-09-26

我试图找到一种快速的方法来比较两个数组并返回数组元素的差异。我得到了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 })];
}

您正在运行的算法将花费O(n^2)时间。最好是对两个数组进行排序,然后用类似于归并的方法找出差异。这需要O(n*logn)时间