用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
当前回答
解决它 从索引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:该算法仅适用于数字和普通字符串,任意对象数组的交集可能无法工作。
其他回答
希望这有助于所有版本。
function diffArray(arr1, arr2) {
var newArr = [];
var large = arr1.length>=arr2.length?arr1:arr2;
var small = JSON.stringify(large) == JSON.stringify(arr1)?arr2:arr1;
for(var i=0;i<large.length;i++){
var copyExists = false;
for(var j =0;j<small.length;j++){
if(large[i]==small[j]){
copyExists= true;
break;
}
}
if(!copyExists)
{
newArr.push(large[i]);
}
}
for(var i=0;i<small.length;i++){
var copyExists = false;
for(var j =0;j<large.length;j++){
if(large[j]==small[i]){
copyExists= true;
break;
}
}
if(!copyExists)
{
newArr.push(small[i]);
}
}
return newArr;
}
如果你的数组是排序的,这应该运行在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;
}
//在线性时间内返回数组a中也在b中的元素: 函数相交(a, b) { 返回a.filter (Set.prototype。new Set(b)); } / /例如: console.log(相交([1,2,3],[2、3、4、5]));
我推荐上述简洁的解决方案,它在大输入上优于其他实现。如果在小输入上的性能很重要,请检查下面的替代方案。
备选方案和性能比较:
有关替代实现,请参阅下面的代码片段,并检查https://jsperf.com/array-intersection-comparison以进行性能比较。
function intersect_for(a, b) { const result = []; const alen = a.length; const blen = b.length; for (let i = 0; i < alen; ++i) { const ai = a[i]; for (let j = 0; j < blen; ++j) { if (ai === b[j]) { result.push(ai); break; } } } return result; } function intersect_filter_indexOf(a, b) { return a.filter(el => b.indexOf(el) !== -1); } function intersect_filter_in(a, b) { const map = b.reduce((map, el) => {map[el] = true; return map}, {}); return a.filter(el => el in map); } function intersect_for_in(a, b) { const result = []; const map = {}; for (let i = 0, length = b.length; i < length; ++i) { map[b[i]] = true; } for (let i = 0, length = a.length; i < length; ++i) { if (a[i] in map) result.push(a[i]); } return result; } function intersect_filter_includes(a, b) { return a.filter(el => b.includes(el)); } function intersect_filter_has_this(a, b) { return a.filter(Set.prototype.has, new Set(b)); } function intersect_filter_has_arrow(a, b) { const set = new Set(b); return a.filter(el => set.has(el)); } function intersect_for_has(a, b) { const result = []; const set = new Set(b); for (let i = 0, length = a.length; i < length; ++i) { if (set.has(a[i])) result.push(a[i]); } return result; }
Firefox 53的结果:
Ops/sec on large arrays (10,000 elements): filter + has (this) 523 (this answer) for + has 482 for-loop + in 279 filter + in 242 for-loops 24 filter + includes 14 filter + indexOf 10 Ops/sec on small arrays (100 elements): for-loop + in 384,426 filter + in 192,066 for-loops 159,137 filter + includes 104,068 filter + indexOf 71,598 filter + has (this) 43,531 (this answer) filter + has (arrow function) 35,588
下面是一个使用可选的比较函数处理多个数组的简单实现:
函数交叉(数组,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)
这是一个现代和简单的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