用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
用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;
});
});
}