在 javascript 中实现数组交集的最简单、无库的代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并得到
[2, 3]
在 javascript 中实现数组交集的最简单、无库的代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并得到
[2, 3]
使用的组合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
改用。
破坏性似乎最简单,特别是如果我们可以假设输入已排序:
/* 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;
}
如果您的环境支持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
。
使用 Underscore.js或lodash.js
_.intersection( [0,345,324] , [1,0,324] ) // gives [0,324]
// Return elements of array a that are also in b in linear time:
function intersect(a, b) {
return a.filter(Set.prototype.has, new Set(b));
}
// Example:
console.log(intersect([1,2,3], [2,3,4,5]));
我推荐上述简洁的解决方案,它在大输入上优于其他实现。如果小输入的性能很重要,请检查下面的替代方案。
替代方案和性能比较:
有关替代实现,请参阅以下代码段,并检查https://jsperf.com/array-intersection-comparison以进行性能比较。
在 Firefox 53 中的结果:
大型阵列(10,000 个元素)上的操作数/秒:
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
小阵列(100 个元素)上的操作数/秒:
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