在 javascript 中实现数组交集的最简单、无库的代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并得到
[2, 3]
break
添加到 Simple js loops
将 ops/sec 增加到 ~10M
使用 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;
});
注意! .includes
和 .indexOf
都使用 ===
在内部比较数组中的元素,因此如果数组包含对象,它将只比较对象引用(而不是它们的内容)。如果要指定自己的比较逻辑,请改用 Array.prototype.some
。
Destructive 似乎最简单,尤其是如果我们可以假设输入已排序:
/* destructively finds the intersection of
* two arrays in a simple fashion.
*
* PARAMS
* a - first array, must already be sorted
* b - second array, must already be sorted
*
* NOTES
* State of input arrays is undefined when
* the function returns. They should be
* (prolly) be dumped.
*
* Should have O(n) operations, where n is
* n = MIN(a.length, b.length)
*/
function intersection_destructive(a, b)
{
var result = [];
while( a.length > 0 && b.length > 0 )
{
if (a[0] < b[0] ){ a.shift(); }
else if (a[0] > b[0] ){ b.shift(); }
else /* they're equal */
{
result.push(a.shift());
b.shift();
}
}
return result;
}
非破坏性必须是更复杂的头发,因为我们必须跟踪索引:
/* finds the intersection of
* two arrays in a simple fashion.
*
* PARAMS
* a - first array, must already be sorted
* b - second array, must already be sorted
*
* NOTES
*
* Should have O(n) operations, where n is
* n = MIN(a.length(), b.length())
*/
function intersect_safe(a, b)
{
var ai=0, bi=0;
var result = [];
while( ai < a.length && bi < b.length )
{
if (a[ai] < b[bi] ){ ai++; }
else if (a[ai] > b[bi] ){ bi++; }
else /* they're equal */
{
result.push(a[ai]);
ai++;
bi++;
}
}
return result;
}
.shift
需要移动数组中的每个元素(O(n) 本身),因此关于第一个版本的复杂性的评论是错误的
如果您的环境支持 ECMAScript 6 Set,一种简单且据称有效(参见规范链接)的方式:
function intersect(a, b) {
var setA = new Set(a);
var setB = new Set(b);
var intersection = new Set([...setA].filter(x => setB.has(x)));
return Array.from(intersection);
}
更短,但可读性更差(也没有创建额外的交集 Set
):
function intersect(a, b) {
var setB = new Set(b);
return [...new Set(a)].filter(x => setB.has(x));
}
请注意,使用集合时,您只会得到不同的值,因此 new Set([1, 2, 3, 3]).size
的计算结果为 3
。
[...setA]
语法?某种特殊的javascript操作?
Set
的字面定义,而不是实现细节。
a
和 intersection
创建一个集合。只要其中一个就足够了。
使用 Underscore.js 或 lodash.js
_.intersection( [0,345,324] , [1,0,324] ) // gives [0,324]
arrA.filter(e=>e.includes(arrB))
还是 _.intersection(arrA, arrB)
?
[ [ { tokenId: 2 } ], [ { tokenId: 2 }, { tokenId: 3 } ] ]
并期望它返回 { tokenId: 2 }
?
javascript var objects = [ [ { tokenId: 2 } ] ] var others = [ [ { tokenId: 2 }, { tokenId: 3 } ] ] _.intersectionWith(objects, others, (a, b) => _.intersectionWith(a, b));
// 返回数组 a 在线性时间内也在 b 中的元素: function intersect(a, b) { return a.filter(Set.prototype.has, new Set(b)); } // 示例:console.log(intersect([1,2,3], [2,3,4,5]));
我推荐上面简洁的解决方案,它在大输入上优于其他实现。如果小输入的性能很重要,请检查以下替代方案。
替代方案和性能比较:
有关替代实现的信息,请参阅以下代码段,并检查 https://jsperf.com/array-intersection-comparison 以进行性能比较。
函数 intersect_for(a, b) { 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);休息; } } } 返回结果; } 函数 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); } 函数 intersect_for_in(a, b) { 常量结果 = [];常量映射 = {}; 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]); } 返回结果; } 函数 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);返回 a.filter(el => set.has(el)); } 函数 intersect_for_has(a, b) { 常量结果 = [];常量集 = 新集(b); for (let i = 0, length = a.length; i < length; ++i) { if (set.has(a[i])) result.push(a[i]); } 返回结果; }
Firefox 53 中的结果:
大型数组(10,000 个元素)上的 Ops/sec:filter + has (this) 523 (this answer) for + has 482 for-loop + in 279 filter + in 242 for-loops 24 filter +包括 14 filter + indexOf 10
小数组(100 个元素)上的操作/秒:for 循环 + 在 384,426 过滤器中 + 在 192,066 循环中 159,137 过滤器 + 包括 104,068 过滤器 + indexOf 71,598 过滤器 + 有(这个)43,531(这个答案)过滤器 + 有(箭头函数) 35,588
intersect([1,2,2,3], [2,3,4,5])
返回 [2, 2, 3]
。
has
在内部使用 indexOf
。它被认为是O(n)。所以给定的解决方案不是线性的。
我在 ES6 方面的贡献。一般来说,它会找到一个数组与作为参数提供的不定数量数组的交集。
Array.prototype.intersect = function(...a) { return [this,...a].reduce((p,c) => p.filter(e => c.includes(e))); } var arrs = [[0,2,4,6,8],[4,5,6,7],[4,6]], arr = [0,1,2,3,4,5,6 ,7,8,9]; document.write("
" + JSON.stringify(arr.intersect(...arrs)) + "");
[[0,1,2,3,4,5,6,7,8,9],[0,2,4,6,8],[4,5,6,7],[4,6]]
的数组中,然后应用 .reduce()
。执行第一个 [0,1,2,3,4,5,6,7,8,9].filter( e => [0,2,4,6,8].includes(e)
操作,结果变成新的 p
,而 c
在下一回合变成 [4,5,6,7]
,并继续如此下去,直到没有剩下的 c
。
prototype
。
只使用关联数组怎么样?
function intersect(a, b) {
var d1 = {};
var d2 = {};
var results = [];
for (var i = 0; i < a.length; i++) {
d1[a[i]] = true;
}
for (var j = 0; j < b.length; j++) {
d2[b[j]] = true;
}
for (var k in d1) {
if (d2[k])
results.push(k);
}
return results;
}
编辑:
// new version
function intersect(a, b) {
var d = {};
var results = [];
for (var i = 0; i < b.length; i++) {
d[b[i]] = true;
}
for (var j = 0; j < a.length; j++) {
if (d[a[j]])
results.push(a[j]);
}
return results;
}
Object.prototype
混淆,这才有可能。
d[b[i]] = true;
而不是 d[b[j]] = true;
(i
不是 j
)。但编辑需要 6 个字符。
通过使用 .pop 而不是 .shift,可以提高 @atk 对已排序基元数组的实现的性能。
function intersect(array1, array2) {
var result = [];
// Don't destroy the original arrays
var a = array1.slice(0);
var b = array2.slice(0);
var aLast = a.length - 1;
var bLast = b.length - 1;
while (aLast >= 0 && bLast >= 0) {
if (a[aLast] > b[bLast] ) {
a.pop();
aLast--;
} else if (a[aLast] < b[bLast] ){
b.pop();
bLast--;
} else /* they're equal */ {
result.push(a.pop());
b.pop();
aLast--;
bLast--;
}
}
return result;
}
我使用 jsPerf 创建了一个基准:http://bit.ly/P9FrZK。使用 .pop 大约快三倍。
a[aLast] > b[bLast]
替换为 a[aLast].localeCompare(b[bLast]) > 0
(与下面的 else if
相同),那么这将适用于字符串。
.pop
是 O(1) 而 .shift()
是 O(n)
从索引 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:该算法仅适用于数字和普通字符串,任意对象数组的交集可能不起作用。
使用 jQuery:
var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);
c = $(b).filter(a);
,但我不建议依赖 jQuery 进行这种数组操作,因为文档只提到它适用于元素。
如果您需要让它处理相交的多个数组:
const intersect = (a1, a2, ...rest) => { const a12 = a1.filter(value => a2.includes(value)) if (rest.length === 0) { return a12; } 返回相交(a12,...休息); }; console.log(intersect([1,2,3,4,5], [1,2], [1, 2, 3,4,5], [2, 10, 1]))
new Set(b).has(x)
甚至比仅使用 b.includes(x)
还要慢。
对此处最小的一个(filter/indexOf solution)进行微小调整,即使用 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() 慢一个常数因子),但似乎是一个很好的平衡。它非常简单,同时提供良好的性能,并且不需要预先排序的输入。
对于仅包含字符串或数字的数组,您可以根据其他一些答案进行排序。对于任意对象数组的一般情况,我认为您无法避免长期这样做。以下将为您提供作为参数提供给 arrayIntersection
的任意数量数组的交集:
var arrayContains = Array.prototype.indexOf ?
function(arr, val) {
return arr.indexOf(val) > -1;
} :
function(arr, val) {
var i = arr.length;
while (i--) {
if (arr[i] === val) {
return true;
}
}
return false;
};
function arrayIntersection() {
var val, arrayCount, firstArray, i, j, intersection = [], missing;
var arrays = Array.prototype.slice.call(arguments); // Convert arguments into a real array
// Search for common values
firstArray = arrays.pop();
if (firstArray) {
j = firstArray.length;
arrayCount = arrays.length;
while (j--) {
val = firstArray[j];
missing = false;
// Check val is present in each remaining array
i = arrayCount;
while (!missing && i--) {
if ( !arrayContains(arrays[i], val) ) {
missing = true;
}
}
if (!missing) {
intersection.push(val);
}
}
}
return intersection;
}
arrayIntersection( [1, 2, 3, "a"], [1, "a", 2], ["a", 1] ); // Gives [1, "a"];
firstArr
或 firstArray
的想法,并且没有更新所有引用。固定的。
另一种能够一次处理任意数量的数组的索引方法:
// Calculate intersection of multiple array or object values.
function intersect (arrList) {
var arrLength = Object.keys(arrList).length;
// (Also accepts regular objects as input)
var index = {};
for (var i in arrList) {
for (var j in arrList[i]) {
var v = arrList[i][j];
if (index[v] === undefined) index[v] = 0;
index[v]++;
};
};
var retv = [];
for (var i in index) {
if (index[i] == arrLength) retv.push(i);
};
return retv;
};
它仅适用于可以作为字符串评估的值,您应该将它们作为数组传递,例如:
intersect ([arr1, arr2, arr3...]);
...但它透明地接受对象作为参数或任何要相交的元素(总是返回公共值的数组)。例子:
intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4]
intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"]
编辑:我只是注意到这在某种程度上有点错误。
那就是:我编码它认为输入数组本身不能包含重复(因为提供的示例没有)。
但是如果输入数组碰巧包含重复,那会产生错误的结果。示例(使用以下实现):
intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]);
// Expected: [ '1' ]
// Actual: [ '1', '3' ]
幸运的是,这很容易通过简单地添加二级索引来解决。那是:
改变:
if (index[v] === undefined) index[v] = 0;
index[v]++;
经过:
if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.
...和:
if (index[i] == arrLength) retv.push(i);
经过:
if (Object.keys(index[i]).length == arrLength) retv.push(i);
完整示例:
// Calculate intersection of multiple array or object values.
function intersect (arrList) {
var arrLength = Object.keys(arrList).length;
// (Also accepts regular objects as input)
var index = {};
for (var i in arrList) {
for (var j in arrList[i]) {
var v = arrList[i][j];
if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.
};
};
var retv = [];
for (var i in index) {
if (Object.keys(index[i]).length == arrLength) retv.push(i);
};
return retv;
};
intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // [ '1' ]
var v =
行后添加 if (typeof v == 'function') continue;
,它将跳过向结果中添加函数。谢谢!
if (typeof v == 'function')
,那么我们可以使用它的字符串化(v.toString()
)作为索引的键。但是,我们需要做一些事情保持它完好无损。最简单的方法是将原始函数分配为值而不是简单的布尔真值。但是,在这种情况下,还应更改最新的索引以检测这种情况并恢复正确的值(功能)。
由于对数据有一些限制,您可以在线性时间内完成!
对于正整数:使用数组将值映射到“已见/未见”布尔值。
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;
}
当然,您需要确保密钥之前没有出现,否则您将破坏您的数据......
function intersection(A,B){
var result = new Array();
for (i=0; i<A.length; i++) {
for (j=0; j<B.length; j++) {
if (A[i] == B[j] && $.inArray(A[i],result) == -1) {
result.push(A[i]);
}
}
}
return result;
}
为简单起见:
// 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 引擎或内核工作,但如果您无法在基于事件的应用程序中运行它,那么您的设计就有更大的问题。
.some(x => x === item)
是编写 .includes(item)
的复杂方式,而 .reduce(removeDuplicates, [])
是编写 flatten + unique 的复杂方式。这也可能比您想象的要慢(与基于事件的应用程序很容易相关)。
我将贡献对我最有效的东西:
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;
};
}
ES2015 的函数式方法
函数式方法必须考虑只使用没有副作用的纯函数,每个函数只涉及一个工作。
这些限制增强了所涉及功能的可组合性和可重用性。
// 小的、可重用的辅助函数 const createSet = xs => new Set(xs);常量过滤器 = f => xs => xs.filter(apply(f));常量应用 = f => x => f(x); // 交集 const intersect = xs => ys => { const zs = createSet(ys); return filter(x => zs.has(x) ? true : false ) (xs); }; // 模拟数据 const xs = [1,2,2,3,4,5];常量 ys = [0,1,2,3,3,3,6,7,8,9]; // 运行 console.log( intersect(xs) (ys) );
请注意,使用了本机 Set
类型,它具有优越的查找性能。
避免重复
显然,第一个 Array
中重复出现的项目被保留,而第二个 Array
被重复数据删除。这可能是也可能不是所需的行为。如果您需要一个独特的结果,只需将 dedupe
应用于第一个参数:
// 辅助函数 const apply = f => x => f(x); const comp = f => g => x => f(g(x));常量 afrom = apply(Array.from); const createSet = xs => new Set(xs);常量过滤器 = f => xs => xs.filter(apply(f)); // 交集 const intersect = xs => ys => { const zs = createSet(ys); return filter(x => zs.has(x) ? true : false ) (xs); }; // 去重 const dedupe = comp(afrom) (createSet); // 模拟数据 const xs = [1,2,2,3,4,5];常量 ys = [0,1,2,3,3,3,6,7,8,9]; // 唯一结果 console.log( intersect(dedupe(xs)) (ys) );
计算任意数量数组的交集
如果您想计算任意数量的 Array
的交集,只需将 intersect
与 foldl
组合起来。这是一个便利功能:
// 辅助函数 const apply = f => x => f(x); const uncurry = f => (x, y) => f(x) (y); const createSet = xs => new Set(xs);常量过滤器 = f => xs => xs.filter(apply(f)); const foldl = f => acc => xs => xs.reduce(uncurry(f), acc); // 交集 const intersect = xs => ys => { const zs = createSet(ys); return filter(x => zs.has(x) ? true : false ) (xs); }; // 任意数量数组的交集 const intersectn = (head, ...tail) => foldl(intersect) (head) (tail); // 模拟数据 const xs = [1,2,2,3,4,5];常量 ys = [0,1,2,3,3,3,6,7,8,9];常量 zs = [0,1,2,3,4,5,6]; // 运行 console.log( intersectn(xs, ys, zs) );
(expr ? true : false)
是多余的。如果不需要实际的布尔值,只使用 expr
,只使用真值/假值。
intersectn
效率低下。这是编写可重用函数的错误方法。
.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;
});
}
我发现这种方法很容易推理。它在恒定时间内执行。
我编写了一个 intesection 函数,它甚至可以根据这些对象的特定属性检测对象数组的交集。
例如,
if arr1 = [{id: 10}, {id: 20}]
and arr2 = [{id: 20}, {id: 25}]
我们想要基于 id
属性的交集,那么输出应该是:
[{id: 20}]
因此,相同的功能(注意:ES6 代码)是:
const intersect = (arr1, arr2, accessors = [v => v, v => v]) => {
const [fn1, fn2] = accessors;
const set = new Set(arr2.map(v => fn2(v)));
return arr1.filter(value => set.has(fn1(value)));
};
您可以将函数调用为:
intersect(arr1, arr2, [elem => elem.id, elem => elem.id])
另请注意:考虑到第一个数组是主数组,此函数会找到交集,因此交集结果将是主数组的结果。
此函数利用字典的强大功能避免了 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;
}
Object.prototype.toString.call(/f/)
(相当于 "[object RegExp]"
)的用途是什么?
Object.prototype.toString.call(elem)
允许为具有相同 toString()
输出的 object
类型的元素保留不同的键
这是 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#section-62
使用一个数组创建一个 Object 并遍历第二个数组以检查该值是否作为键存在。
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;
}
我认为在内部使用对象可以帮助计算并且也可以是高性能的。
// 方法维护每个元素的计数,也适用于负元素
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]
我正在使用地图,甚至可以使用对象。
//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;
}
我扩展了 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;
}
如果您的数组已排序,这应该在 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;
}
var arrays = [ [1, 2, 3], [2, 3, 4, 5] ] function commonValue (...arr) { let res = arr[0].filter(function (x) { return arr.every ((y) => y.includes(x)) }) 返回资源; } commonValue(...数组);
function intersectionOfArrays(arr1, arr2) {
return arr1.filter((element) => arr2.indexOf(element) !== -1).filter((element, pos, self) => self.indexOf(element) == pos);
}
intersection([1,2,1,1,3], [1])
返回[1, 1, 1]
。它不应该只返回[1]
吗?