用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
当前回答
“filter”和“indexOf”在IE中的Array上不支持。这个怎么样:
var array1 = [1, 2, 3];
var array2 = [2, 3, 4, 5];
var intersection = [];
for (i in array1) {
for (j in array2) {
if (array1[i] == array2[j]) intersection.push(array1[i]);
}
}
其他回答
解决它 从索引0开始逐一检查,然后创建一个新数组。
像这样的东西,不过测试不太好。
function intersection(x,y){
x.sort();y.sort();
var i=j=0;ret=[];
while(i<x.length && j<y.length){
if(x[i]<y[j])i++;
else if(y[j]<x[i])j++;
else {
ret.push(x[i]);
i++,j++;
}
}
return ret;
}
alert(intersection([1,2,3], [2,3,4,5]));
PS:该算法仅适用于数字和普通字符串,任意对象数组的交集可能无法工作。
我使用地图甚至对象可以使用。
//find intersection of 2 arrs
const intersections = (arr1,arr2) => {
let arrf = arr1.concat(arr2)
let map = new Map();
let union = [];
for(let i=0; i<arrf.length; i++){
if(map.get(arrf[i])){
map.set(arrf[i],false);
}else{
map.set(arrf[i],true);
}
}
map.forEach((v,k)=>{if(!v){union.push(k);}})
return union;
}
对这里最小的一个(filter/indexOf解决方案)稍作调整,即使用JavaScript对象在其中一个数组中创建值的索引,将从O(N*M)减少到“可能”线性时间。source1 source2
function intersect(a, b) {
var aa = {};
a.forEach(function(v) { aa[v]=1; });
return b.filter(function(v) { return v in aa; });
}
这不是最简单的解决方案(它的代码比filter+indexOf要多),也不是最快的解决方案(可能比intersect_safe()慢一个常数因子),但似乎是一个很好的平衡。它非常简单,同时提供了良好的性能,并且不需要预先排序的输入。
ES2015的函数式方法
函数式方法必须考虑只使用没有副作用的纯函数,每个函数只与单个作业有关。
这些限制增强了所涉及函数的可组合性和可重用性。
//小的,可重用的辅助函数 const createSet = xs => new Set(xs); Const filter = f => xs => xs.filter(apply(f)); Const apply = f => x => f(x); / /十字路口 Const相交= xs => ys => { const zs =创建集(ys); 返回过滤器(x => zs.has(x)) ? 真正的 :假 ) (x); }; //模拟数据 Const xs = [1,2,2,3,4,5]; Const ys = [0,1,2,3,3,3,6,7,8,9]; //运行 Console.log (intersect(xs) (ys));
请注意,使用本机Set类型,这有一个优点 查找性能。
避免重复
显然,第一个数组中重复出现的项将被保留,而第二个数组将被去重。这可能是也可能不是理想的行为。如果你需要一个唯一的结果,只需对第一个参数应用重复数据删除:
// auxiliary functions const apply = f => x => f(x); const comp = f => g => x => f(g(x)); const afrom = apply(Array.from); const createSet = xs => new Set(xs); const filter = f => xs => xs.filter(apply(f)); // intersection const intersect = xs => ys => { const zs = createSet(ys); return filter(x => zs.has(x) ? true : false ) (xs); }; // de-duplication const dedupe = comp(afrom) (createSet); // mock data const xs = [1,2,2,3,4,5]; const ys = [0,1,2,3,3,3,6,7,8,9]; // unique result console.log( intersect(dedupe(xs)) (ys) );
计算任意数量数组的交集
如果你想计算任意数量的数组的交点,只需用compose intersect和foldl。这是一个方便函数:
// auxiliary functions const apply = f => x => f(x); const uncurry = f => (x, y) => f(x) (y); const createSet = xs => new Set(xs); const filter = f => xs => xs.filter(apply(f)); const foldl = f => acc => xs => xs.reduce(uncurry(f), acc); // intersection const intersect = xs => ys => { const zs = createSet(ys); return filter(x => zs.has(x) ? true : false ) (xs); }; // intersection of an arbitrarily number of Arrays const intersectn = (head, ...tail) => foldl(intersect) (head) (tail); // mock data const xs = [1,2,2,3,4,5]; const ys = [0,1,2,3,3,3,6,7,8,9]; const zs = [0,1,2,3,4,5,6]; // run console.log( intersectn(xs, ys, zs) );
该函数利用字典的强大功能,避免了N^2问题。每个数组只循环一次,第三次更短的循环返回最终结果。 它还支持数字、字符串和对象。
function array_intersect(array1, array2)
{
var mergedElems = {},
result = [];
// Returns a unique reference string for the type and value of the element
function generateStrKey(elem) {
var typeOfElem = typeof elem;
if (typeOfElem === 'object') {
typeOfElem += Object.prototype.toString.call(elem);
}
return [typeOfElem, elem.toString(), JSON.stringify(elem)].join('__');
}
array1.forEach(function(elem) {
var key = generateStrKey(elem);
if (!(key in mergedElems)) {
mergedElems[key] = {elem: elem, inArray2: false};
}
});
array2.forEach(function(elem) {
var key = generateStrKey(elem);
if (key in mergedElems) {
mergedElems[key].inArray2 = true;
}
});
Object.values(mergedElems).forEach(function(elem) {
if (elem.inArray2) {
result.push(elem.elem);
}
});
return result;
}
如果有无法解决的特殊情况,仅通过修改generateStrKey函数就可以解决。这个函数的诀窍在于,它根据类型和值唯一地表示每个不同的数据。
这个变体有一些性能改进。在任何数组为空的情况下避免循环。它还首先遍历较短的数组,因此如果它在第二个数组中找到了第一个数组的所有值,则退出循环。
function array_intersect(array1, array2)
{
var mergedElems = {},
result = [],
firstArray, secondArray,
firstN = 0,
secondN = 0;
function generateStrKey(elem) {
var typeOfElem = typeof elem;
if (typeOfElem === 'object') {
typeOfElem += Object.prototype.toString.call(elem);
}
return [typeOfElem, elem.toString(), JSON.stringify(elem)].join('__');
}
// Executes the loops only if both arrays have values
if (array1.length && array2.length)
{
// Begins with the shortest array to optimize the algorithm
if (array1.length < array2.length) {
firstArray = array1;
secondArray = array2;
} else {
firstArray = array2;
secondArray = array1;
}
firstArray.forEach(function(elem) {
var key = generateStrKey(elem);
if (!(key in mergedElems)) {
mergedElems[key] = {elem: elem, inArray2: false};
// Increases the counter of unique values in the first array
firstN++;
}
});
secondArray.some(function(elem) {
var key = generateStrKey(elem);
if (key in mergedElems) {
if (!mergedElems[key].inArray2) {
mergedElems[key].inArray2 = true;
// Increases the counter of matches
secondN++;
// If all elements of first array have coincidence, then exits the loop
return (secondN === firstN);
}
}
});
Object.values(mergedElems).forEach(function(elem) {
if (elem.inArray2) {
result.push(elem.elem);
}
});
}
return result;
}