javascript中数组交集的最简单代码

IT技术 javascript data-structures intersection
2021-01-03 16:30:27

在 javascript 中实现数组交集的最简单、无库的代码是什么?我想写

intersection([1,2,3], [2,3,4,5])

并得到

[2, 3]
6个回答

使用的组合Array.prototype.filterArray.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改用。

对于那些好奇的人来说,让这个工作的 IE 的最低版本是:9
2021-02-11 16:30:27
intersection([1,2,1,1,3], [1])返回[1, 1, 1]它不应该返回[1]吗?
2021-02-24 16:30:27
这不是非常低效吗,是 O(n^2)。
2021-02-25 16:30:27
最佳答案在这里,无论是为了简单还是使用非数字
2021-03-01 16:30:27
接得好。您将需要第二个过滤器。请参阅此处的示例: stackoverflow.com/a/16227294/390519(<-- 在该答案的末尾)
2021-03-08 16:30:27

破坏性似乎最简单,特别是如果我们可以假设输入已排序:

/* 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)),因此关于第一个版本复杂性的注释是错误的
2021-02-08 16:30:27
我发现了一些关于 shift() 与 pop() 的表现:jsperf.com/pop-vs-shift-on-a-array/11
2021-02-09 16:30:27
@thesmart:你是对的,肯定有更高效的方法来做到这一点。上面的代码旨在简单,而不是快速:)
2021-02-22 16:30:27
不,当其中一个数组完成时循环停止,不一定是较短的数组。检查这个例子
2021-02-26 16:30:27
它是 array.shift 每次调用都会在后台创建一个新数组?
2021-02-27 16:30:27

如果您的环境支持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

在第一个示例中(删除重复项),无需从a和 中创建集合intersection只需其中一个就足够了。
2021-02-09 16:30:27
这是什么[...setA]语法?某种特殊的javascript操作?
2021-02-12 16:30:27
@nbarbosa 我很好奇:你为什么“克隆”数组 a?#filter 不会破坏原始数组,对吗?它创建了一个新数组?
2021-02-13 16:30:27
“请注意, set 实现将只允许唯一值” - 这是 a 的字面定义Set,而不是实现细节。
2021-02-22 16:30:27
@jxramos 是 Spread 语法,在这种情况下,它仅用于从集合中的元素创建数组。“Array.from(setA)”在这种情况下也可以工作,但由于问题要求“最简单”,我试图让它更清晰地阅读该行。就此而言,我认为代码可以更简单,所以我将更新代码段。
2021-03-02 16:30:27

使用 Underscore.jslodash.js

_.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]
Op要求“无图书馆”。
2021-02-15 16:30:27
无论如何,这是此搜索的顶级谷歌列表,因此拥有图书馆答案很有用。谢谢。
2021-03-02 16:30:27

// 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
    
intersect([1,2,2,3], [2,3,4,5])返回[2, 2, 3]
2021-02-11 16:30:27
@SeregPie 没错。根据评论“返回也在 b 中的数组 a 的元素”
2021-02-12 16:30:27
@xdeepakv:不,不是。不知道你从哪里得到这个想法。
2021-02-18 16:30:27
高质量的答案,但是 Sets 的使用从根本上改变了结果,因为 op 的问题只询问了数组交集,并没有提及/规定如何处理重复项。害羞的是,当存在重复项时,此答案可能会产生意想不到的结果。
2021-02-27 16:30:27
has内部使用indexOf. 它被视为O(n)所以给定的解决方案不是线性的。
2021-03-03 16:30:27