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

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

并获得

[2, 3]

当前回答

通过使用.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创建了一个基准测试。使用。pop要快三倍。

其他回答

如果你的数组是排序的,这应该运行在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;
}

这是一个提议的标准:对于当前阶段2的提议https://github.com/tc39/proposal-set-methods,您可以使用

mySet.intersection(mySet2);

在此之前,你可以使用Immutable.js的Set,它激发了这个提议

Immutable.Set(mySet).intersect(mySet2)

.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;
  });
}

我发现这种方法很容易解释。它在常数时间内运行。

我在ES6方面的贡献。一般来说,它会找到一个数组与作为参数提供的不确定数量的数组的交集。

Array.prototype.intersect = function(…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]; 文档。以前写(“< >”+ JSON.stringify (arr.intersect (arr)) + " < / pre > ");

简单性:

// 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引擎或内核工作,但如果你在基于事件的应用程序中运行时遇到问题,那么你的设计就有更大的问题。