用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
当前回答
这是一个现代和简单的ES6方式来做,也非常灵活。 它允许您指定多个数组作为与主题数组进行比较的数组,并且可以在包含和独占模式下工作。
// =======================================
// The function
// =======================================
function assoc(subjectArray, otherArrays, { mustBeInAll = true } = {}) {
return subjectArray.filter((subjectItem) => {
if (mustBeInAll) {
return otherArrays.every((otherArray) =>
otherArray.includes(subjectItem)
);
} else {
return otherArrays.some((otherArray) => otherArray.includes(subjectItem));
}
});
}
// =======================================
// The usage
// =======================================
const cheeseList = ["stilton", "edam", "cheddar", "brie"];
const foodListCollection = [
["cakes", "ham", "stilton"],
["juice", "wine", "brie", "bread", "stilton"]
];
// Output will be: ['stilton', 'brie']
const inclusive = assoc(cheeseList, foodListCollection, { mustBeInAll: false }),
// Output will be: ['stilton']
const exclusive = assoc(cheeseList, foodListCollection, { mustBeInAll: true })
实例:https://codesandbox.io/s/zealous-butterfly-h7dgf?fontsize=14&hidenavigation=1&theme=dark
其他回答
简单性:
// Usage
const intersection = allLists
.reduce(intersect, allValues)
.reduce(removeDuplicates, []);
// Implementation
const intersect = (intersection, list) =>
intersection.filter(item =>
list.some(x => x === item));
const removeDuplicates = (uniques, item) =>
uniques.includes(item) ? uniques : uniques.concat(item);
// Example Data
const somePeople = [bob, doug, jill];
const otherPeople = [sarah, bob, jill];
const morePeople = [jack, jill];
const allPeople = [...somePeople, ...otherPeople, ...morePeople];
const allGroups = [somePeople, otherPeople, morePeople];
// Example Usage
const intersection = allGroups
.reduce(intersect, allPeople)
.reduce(removeDuplicates, []);
intersection; // [jill]
好处:
泥土简单 以数据为中心的 适用于任意数量的列表 适用于任意长度的列表 适用于任意类型的值 适用于任意排序顺序 保留形状(在任何数组中首次出现的顺序) 尽可能早退出 内存安全,不影响函数/数组原型
缺点:
内存占用率较高 更高的CPU使用率 需要理解reduce 需要理解数据流
你不希望将其用于3D引擎或内核工作,但如果你在基于事件的应用程序中运行时遇到问题,那么你的设计就有更大的问题。
我认为在内部使用一个对象可以帮助计算,也可以提高性能。
//方法维护每个元素的计数,也适用于负元素
function intersect(a,b){
const A = {};
a.forEach((v)=>{A[v] ? ++A[v] : A[v] = 1});
const B = {};
b.forEach((v)=>{B[v] ? ++B[v] : B[v] = 1});
const C = {};
Object.entries(A).map((x)=>C[x[0]] = Math.min(x[1],B[x[0]]))
return Object.entries(C).map((x)=>Array(x[1]).fill(Number(x[0]))).flat();
}
const x = [1,1,-1,-1,0,0,2,2];
const y = [2,0,1,1,1,1,0,-1,-1,-1];
const result = intersect(x,y);
console.log(result); // (7) [0, 0, 1, 1, 2, -1, -1]
这是一个提议的标准:对于当前阶段2的提议https://github.com/tc39/proposal-set-methods,您可以使用
mySet.intersection(mySet2);
在此之前,你可以使用Immutable.js的Set,它激发了这个提议
Immutable.Set(mySet).intersect(mySet2)
对这里最小的一个(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()慢一个常数因子),但似乎是一个很好的平衡。它非常简单,同时提供了良好的性能,并且不需要预先排序的输入。
通过对数据的一些限制,您可以在线性时间内完成!
对于正整数:使用一个数组将值映射到“已见/未见”布尔值。
function intersectIntegers(array1,array2) {
var seen=[],
result=[];
for (var i = 0; i < array1.length; i++) {
seen[array1[i]] = true;
}
for (var i = 0; i < array2.length; i++) {
if ( seen[array2[i]])
result.push(array2[i]);
}
return result;
}
对于对象也有类似的技术:取一个虚拟键,为array1中的每个元素设置为“true”,然后在array2的元素中寻找这个键。完事后收拾一下。
function intersectObjects(array1,array2) {
var result=[];
var key="tmpKey_intersect"
for (var i = 0; i < array1.length; i++) {
array1[i][key] = true;
}
for (var i = 0; i < array2.length; i++) {
if (array2[i][key])
result.push(array2[i]);
}
for (var i = 0; i < array1.length; i++) {
delete array1[i][key];
}
return result;
}
当然,你需要确保这个键之前没有出现过,否则你会破坏你的数据…