在JavaScript中，实现数组交集的最简单、无需使用库的代码是什么？我想编写
intersection([1,2,3], [2,3,4,5])
并获取
[2, 3]
JavaScript中求两个数组交集的最简代码
1018
- Peter
10
40个回答
2
我将分享我个人使用过最有效的方法:
if (!Array.prototype.intersect){
Array.prototype.intersect = function (arr1) {
var r = [], o = {}, l = this.length, i, v;
for (i = 0; i < l; i++) {
o[this[i]] = true;
}
l = arr1.length;
for (i = 0; i < l; i++) {
v = arr1[i];
if (v in o) {
r.push(v);
}
}
return r;
};
}
- Johan
2
使用ES2015的函数式方法
函数式方法必须考虑只使用没有副作用的纯函数，每个函数只关注一个单一任务。
这些限制增强了涉及函数的组合性和可重用性。
// small, reusable auxiliary functions
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const apply = f => x => f(x);
// intersection
const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
// run it
console.log( intersect(xs) (ys) );Set类型具有优越的查找性能。避免重复。
显然，第一个
Array中反复出现的项被保留，而第二个Array被去重。这可能是期望的行为，也可能不是。如果您需要唯一的结果，请将dedupe应用于第一个参数：
// 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) );计算任意数量的Array的交集
如果你想计算任意数量的Array的交集，只需将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) );- user6445533
3
1功能强大：不得不再看一遍才确认那不是 Haskell。唯一的小问题是：
(expr ? true : false) 是多余的。如果实际上不需要布尔值，只需要真/假值，请使用 expr。 - jose_castro_arnaud毫无意义的复杂化，而且
intersectn效率低下。这不是编写可重用函数的正确方式。 - Ry-这个回答值得更深入的批评，而不是“毫无意义的复杂”。如果有人会受到它的影响，那么一个仅仅表示“错误”的评论只会带来困惑。 - Corey
2
使用
.reduce构建一个映射表，使用.filter查找交集。在.filter中使用delete可以使第二个数组像一个唯一的集合一样被处理。function intersection (a, b) {
var seen = a.reduce(function (h, k) {
h[k] = true;
return h;
}, {});
return b.filter(function (k) {
var exists = seen[k];
delete seen[k];
return exists;
});
}
我认为这种方法很容易理解，它在常数时间内执行。
- Belden
1
这里是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;
};
- Dorian
1
如果有underscore的话，这不是一个坏的参考。 - Dimitrios Mistriotis
1
我认为在计算中使用对象可以提高计算效率并且是可行的。
// 该方法可以维护每个元素的计数，同时适用于负元素
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]
- Mayank Narula
1
我正在使用地图，即使可以使用对象。
//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;
}
- abhishek kumar Choudhary
1
“仅有代码的答案不是高质量的答案”。虽然这段代码可能有用，但您可以通过解释它为什么有效、如何有效、何时使用和其局限性是什么来改进它。请编辑您的回答，包括解释并链接到相关文档。 - Stephen Ostermiller
1
使用一个数组创建一个对象，然后循环第二个数组以检查该值是否存在于键中。
function intersection(arr1, arr2) {
var myObj = {};
var myArr = [];
for (var i = 0, len = arr1.length; i < len; i += 1) {
if(myObj[arr1[i]]) {
myObj[arr1[i]] += 1;
} else {
myObj[arr1[i]] = 1;
}
}
for (var j = 0, len = arr2.length; j < len; j += 1) {
if(myObj[arr2[j]] && myArr.indexOf(arr2[j]) === -1) {
myArr.push(arr2[j]);
}
}
return myArr;
}
- sridhar
1
这是一个提议的标准：使用当前阶段2的提议https://github.com/tc39/proposal-set-methods，你可以使用。
mySet.intersection(mySet2);
在那之前，您可以使用Immutable.js的Set，该库启发了该提案。
Immutable.Set(mySet).intersect(mySet2)
- serv-inc
0
如果你的数组已经排序，这段代码应该可以在O(n)时间内运行，其中n是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;
}
- Dave Swanson
0
我扩展了tarulen的答案，使其适用于任意数量的数组。它还应该适用于非整数值。
function intersect() {
const last = arguments.length - 1;
var seen={};
var result=[];
for (var i = 0; i < last; i++) {
for (var j = 0; j < arguments[i].length; j++) {
if (seen[arguments[i][j]]) {
seen[arguments[i][j]] += 1;
}
else if (!i) {
seen[arguments[i][j]] = 1;
}
}
}
for (var i = 0; i < arguments[last].length; i++) {
if ( seen[arguments[last][i]] === last)
result.push(arguments[last][i]);
}
return result;
}
- gabe appleton
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
break添加到Simple js loops中将会使 ops/sec 增加到约10M。 - Richard