用javascript实现数组交叉的最简单、无库代码是什么?我想写

intersection([1,2,3], [2,3,4,5])

并获得

[2, 3]

当前回答

如果你的数组是排序的,这应该运行在O(n),其中n是min(a.length, b.length)

function intersect_1d( a, b ){
    var out=[], ai=0, bi=0, acurr, bcurr, last=Number.MIN_SAFE_INTEGER;
    while( ( acurr=a[ai] )!==undefined && ( bcurr=b[bi] )!==undefined ){
        if( acurr < bcurr){
            if( last===acurr ){
                out.push( acurr );
            }
            last=acurr;
            ai++;
        }
        else if( acurr > bcurr){
            if( last===bcurr ){
                out.push( bcurr );
            }
            last=bcurr;
            bi++;
        }
        else {
            out.push( acurr );
            last=acurr;
            ai++;
            bi++;
        }
    }
    return out;
}

其他回答

下面是underscore.js的实现:

_.intersection = function(array) {
  if (array == null) return [];
  var result = [];
  var argsLength = arguments.length;
  for (var i = 0, length = array.length; i < length; i++) {
    var item = array[i];
    if (_.contains(result, item)) continue;
    for (var j = 1; j < argsLength; j++) {
      if (!_.contains(arguments[j], item)) break;
    }
    if (j === argsLength) result.push(item);
  }
  return result;
};

来源:http://underscorejs.org/docs/underscore.html部分- 62

与效率无关,但很容易理解,这里有一个集合的并和交的例子,它处理集合的数组和集合的集合。

http://jsfiddle.net/zhulien/NF68T/

// process array [element, element...], if allow abort ignore the result
function processArray(arr_a, cb_a, blnAllowAbort_a)
{
    var arrResult = [];
    var blnAborted = false;
    var intI = 0;

    while ((intI < arr_a.length) && (blnAborted === false))
    {
        if (blnAllowAbort_a)
        {
            blnAborted = cb_a(arr_a[intI]);
        }
        else
        {
            arrResult[intI] = cb_a(arr_a[intI]);
        }
        intI++;
    }

    return arrResult;
}

// process array of operations [operation,arguments...]
function processOperations(arrOperations_a)
{
    var arrResult = [];
    var fnOperationE;

    for(var intI = 0, intR = 0; intI < arrOperations_a.length; intI+=2, intR++) 
    {
        var fnOperation = arrOperations_a[intI+0];
        var fnArgs = arrOperations_a[intI+1];
        if (fnArgs === undefined)
        {
            arrResult[intR] = fnOperation();
        }
        else
        {
            arrResult[intR] = fnOperation(fnArgs);
        }
    }

    return arrResult;
}

// return whether an element exists in an array
function find(arr_a, varElement_a)
{
    var blnResult = false;

    processArray(arr_a, function(varToMatch_a)
    {
        var blnAbort = false;

        if (varToMatch_a === varElement_a)
        {
            blnResult = true;
            blnAbort = true;
        }

        return blnAbort;
    }, true);

    return blnResult;
}

// return the union of all sets
function union(arr_a)
{
    var arrResult = [];
    var intI = 0;

    processArray(arr_a, function(arrSet_a)
    {
        processArray(arrSet_a, function(varElement_a)
        {
            // if the element doesn't exist in our result
            if (find(arrResult, varElement_a) === false)
            {
                // add it
                arrResult[intI] = varElement_a;
                intI++;
            }
        });
    });

    return arrResult;
}

// return the intersection of all sets
function intersection(arr_a)
{
    var arrResult = [];
    var intI = 0;

    // for each set
    processArray(arr_a, function(arrSet_a)
    {
        // every number is a candidate
        processArray(arrSet_a, function(varCandidate_a)
        {
            var blnCandidate = true;

            // for each set
            processArray(arr_a, function(arrSet_a)
            {
                // check that the candidate exists
                var blnFoundPart = find(arrSet_a, varCandidate_a);

                // if the candidate does not exist
                if (blnFoundPart === false)
                {
                    // no longer a candidate
                    blnCandidate = false;
                }
            });

            if (blnCandidate)
            {
                // if the candidate doesn't exist in our result
                if (find(arrResult, varCandidate_a) === false)
                {
                    // add it
                    arrResult[intI] = varCandidate_a;
                    intI++;
                }
            }
        });
    });

    return arrResult;
}

var strOutput = ''

var arrSet1 = [1,2,3];
var arrSet2 = [2,5,6];
var arrSet3 = [7,8,9,2];

// return the union of the sets
strOutput = union([arrSet1, arrSet2, arrSet3]);
alert(strOutput);

// return the intersection of 3 sets
strOutput = intersection([arrSet1, arrSet2, arrSet3]);
alert(strOutput);

// of 3 sets of sets, which set is the intersecting set
strOutput = processOperations([intersection,[[arrSet1, arrSet2], [arrSet2], [arrSet2, arrSet3]]]);
alert(strOutput);

下面是一个使用可选的比较函数处理多个数组的简单实现:

函数交叉(数组,compareFn = (val1, val2) => (val1 == val2)) { 如果数组。长度< 2)返回数组[0]?[] Const array1 = arrays[0] const array2 =交集(arrays.slice(1), compareFn) array1返回。过滤器(val1 =>数组2。if (val2 => compareFn(val1, val2))) } console.log(十字路口([[1,2,3],[2、3、4、5]])) console.log(十字路口([[{id: 1}, {id: 2}], [{id: 1}, {id: 3}]], (val1, val2) => val1。Id === val2.id)

function intersectionOfArrays(arr1, arr2) {
    return arr1.filter((element) => arr2.indexOf(element) !== -1).filter((element, pos, self) => self.indexOf(element) == pos);
}

基于Anon的出色回答,这个函数返回两个或多个数组的交集。

function arrayIntersect(arrayOfArrays)
{        
    var arrayCopy = arrayOfArrays.slice(),
        baseArray = arrayCopy.pop();

    return baseArray.filter(function(item) {
        return arrayCopy.every(function(itemList) {
            return itemList.indexOf(item) !== -1;
        });
    });
}