用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
当前回答
这是一个提议的标准:对于当前阶段2的提议https://github.com/tc39/proposal-set-methods,您可以使用
mySet.intersection(mySet2);
在此之前,你可以使用Immutable.js的Set,它激发了这个提议
Immutable.Set(mySet).intersect(mySet2)
其他回答
下面是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
.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;
});
}
我发现这种方法很容易解释。它在常数时间内运行。
我认为在内部使用一个对象可以帮助计算,也可以提高性能。
//方法维护每个元素的计数,也适用于负元素
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]
使用Array.prototype.filter和Array.prototype.includes的组合:
const filteredArray = array1.filter(value => array2.includes(value));
对于较旧的浏览器,使用Array.prototype.indexOf且不使用箭头函数:
var filteredArray = array1.filter(function(n) {
return array2.indexOf(n) !== -1;
});
NB !.includes和. indexof都在内部使用===来比较数组中的元素,所以如果数组包含对象,它只比较对象引用(而不是对象的内容)。如果你想指定自己的比较逻辑,请使用Array.prototype.some。
如果你的数组是排序的,这应该运行在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;
}