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

Question

在javascript中实现数组交叉的最简单,无库的代码是什么？我想写

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

得到

[2, 3]

Answer 1

使用的组合Array.prototype.filter和Array.prototype.indexOf:

array1.filter(value => -1 !== array2.indexOf(value))

Answer 2

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

/* 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;
}

Answer 3

如果您的环境支持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) {
      return [...new Set(a)].filter(x => new Set(b).has(x));
}

避免新Set的b每次:

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.

Answer 4

使用 Underscore.js或lodash.js

_.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]

Answer 5

最简单、最快的O(n)和最短方法：

function intersection (a, b) {
    const setA = new Set(a);
    return b.filter(value => setA.has(value));
}

console.log(intersection([1,2,3], [2,3,4,5]))

@nbarbosa有几乎相同的答案，但他将两个数组转换为Set，然后返回到array. 不同之处在于，他的代码将仅返回唯一记录，而此代码的结果还将包含数组中的重复条目b（假设两个数组都没有填充唯一值）。

因此，请使用适合您要求的代码

Answer 6

我在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("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");

Answer 7

如何使用关联数组呢？

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

Answer 8

// 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以进行性能比较.

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(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
  

• 小数组上的Ops/sec(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
  

Answer 9

1. 解决
2. 从索引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:该算法仅适用于Numbers和Normal Strings,仲裁对象数组的交集可能不起作用.

Answer 10

通过使用.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.

Answer 11

使用jQuery:

var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);

Answer 12

如果您需要让它处理多个数组的相交：

const intersect = (a1, a2, ...rest) => {
  const a12 = a1.filter(value => a2.includes(value))
  if (rest.length === 0) { return a12; }
  return intersect(a12, ...rest);
};

console.log(intersect([1,2,3,4,5], [1,2], [1, 2, 3,4,5], [2, 10, 1])) 

Answer 13

对于仅包含字符串或数字的数组,您可以根据其他一些答案对排序执行某些操作.对于任意对象数组的一般情况,我认为你不能避免长期使用它.以下将为您提供作为参数提供的任意数量的数组的交集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"]; 

Answer 14

使用ES2015和Sets非常简短.接受类似于String的类似数组的值并删除重复项.

let intersection = function(a, b) {
  a = new Set(a), b = new Set(b);
  return [...a].filter(v => b.has(v));
};

console.log(intersection([1,2,1,2,3], [2,3,5,4,5,3]));

console.log(intersection('ccaabbab', 'addb').join(''));

Answer 15

另一种能够同时处理任意数量数组的索引方法:

// 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' ]

Answer 16

对这里最小的一个微调(filter/indexOf解决方案),即使用JavaScript对象在其中一个数组中创建值的索引,将从O(N*M)减少到"可能"的线性时间.源1 源2

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()更慢),但似乎是一个非常好的平衡.它非常简单,同时提供良好的性能,并且不需要预先排序的输入.