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

JavaScript

2020-03-12

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

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

并得到

[2, 3]

第980篇《JavaScript中数组交集的最简单代码》来自Winter(https://github.com/aiyld/aiyld.github.io)的站点

共21个回答

古一蛋蛋 2020.03.12

Here is underscore.js implementation:

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

Source: http://underscorejs.org/docs/underscore.html#section-62

Me无敌 2020.03.12

function getIntersection(arr1, arr2){
    var result = [];
    arr1.forEach(function(elem){
        arr2.forEach(function(elem2){
            if(elem === elem2){
                result.push(elem);
            }
        });
    });
    return result;
}

getIntersection([1,2,3], [2,3,4,5]); // [ 2, 3 ]

ProTony 2020.03.12

A functional approach with ES2015

A functional approach must consider using only pure functions without side effects, each of which is only concerned with a single job.

These restrictions enhance the composability and reusability of the functions involved.

// small, reusable auxiliary functions

const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const apply = f => x => f(x);


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// run it

console.log( intersect(xs) (ys) );

Please note that the native Set type is used, which has an advantageous lookup performance.

Avoid duplicates

Obviously repeatedly occurring items from the first Array are preserved, while the second Array is de-duplicated. This may be or may be not the desired behavior. If you need a unique result just apply dedupe to the first argument:

// auxiliary functions

const apply = f => x => f(x);
const comp = f => g => x => f(g(x));
const afrom = apply(Array.from);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// de-duplication

const dedupe = comp(afrom) (createSet);


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// unique result

console.log( intersect(dedupe(xs)) (ys) );

Compute the intersection of any number of `Array`s

If you want to compute the intersection of an arbitrarily number of Arrays just compose intersect with foldl. Here is a convenience function:

// auxiliary functions

const apply = f => x => f(x);
const uncurry = f => (x, y) => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// intersection of an arbitrarily number of Arrays

const intersectn = (head, ...tail) => foldl(intersect) (head) (tail);


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
const zs = [0,1,2,3,4,5,6];


// run

console.log( intersectn(xs, ys, zs) );

Tony番长 2020.03.12

Rather using indexOf you can also use Array.protype.includes.

function intersection(arr1, arr2) {
  return arr1.filter((ele => {
    return arr2.includes(ele);
  }));
}

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

乐达蒙 2020.03.12

ES6 style simple way.

const intersection = (a, b) => {
  const s = new Set(b);
  return a.filter(x => s.has(x));
};

Example:

intersection([1, 2, 3], [4, 3, 2]); // [2, 3]

JinJinGil 2020.03.12

If you need to have it handle intersecting multiple arrays:

const intersect = (a, b, ...rest) => {
  if (rest.length === 0) return [...new Set(a)].filter(x => new Set(b).has(x));
  return intersect(a, intersect(b, ...rest));
};

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

蛋蛋猴子前端 2020.03.12

"indexOf" for IE 9.0, chrome, firefox, opera,

    function intersection(a,b){
     var rs = [], x = a.length;
     while (x--) b.indexOf(a[x])!=-1 && rs.push(a[x]);
     return rs.sort();
    }

intersection([1,2,3], [2,3,4,5]);
//Result:  [2,3]

达蒙老丝 2020.03.12

对此处的最小调整进行细微调整（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（）慢一个常数），但似乎是一个很好的平衡。它具有非常简单的一面，同时提供了良好的性能，并且不需要预先排序的输入。

凯梅小胖 2020.03.12

You can use (for all browsers except IE):

const intersection = array1.filter(element => array2.includes(element));

or for IE :

const intersection = array1.filter(element => array2.indexOf(element) !== -1);

hide on 2020.03.12

在数据上有一些限制，您可以在线性时间内完成！

对于正整数：使用将值映射到“可见/不可见”布尔值的数组。

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

当然，您需要确保密钥之前没有出现，否则您将破坏数据...

A逆天猿 2020.03.12

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

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

或者，如vrugtehagel在注释中建议的那样，您可以使用更新Array.prototype.includes的代码甚至更简单的代码：

array1.filter(value => array2.includes(value))

对于较旧的浏览器：

array1.filter(function(n) {
    return array2.indexOf(n) !== -1;
});

LEvaGreen 2020.03.12

解决
从索引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：仅适用于数字和普通字符串的算法，任意对象数组的交集可能不起作用。

神无老丝Davaid 2020.03.12

对于仅包含字符串或数字的数组，您可以按照其他一些答案进行排序。对于任意对象数组的一般情况，我认为您不能避免这样做。下面将为您提供作为参数提供的任意数量的数组的交集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"];

小宇宙飞云 2020.03.12

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

逆天小卤蛋Green 2020.03.12

你可以使用一个Set作为thisArg的Array#filter，并采取Set#has回调。

function intersection(a, b) {
    return a.filter(Set.prototype.has, new Set(b));
}

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

Tom蛋蛋 2020.03.12

使用jQuery：

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

不知 2020.03.12

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

MonsterKK梅 2020.03.12

// 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中的结果：

大型阵列（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

泡芙小宇宙十三 2020.03.12

使用 Underscore.js或lodash.js

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

JinJin村村 2020.03.12

仅使用关联数组怎么样？

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

泡芙小胖 2020.03.12

我对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>");

相似问题

基于react18+vite4+zustand网页端仿微信聊天实例

0 回答

基于tauri+vite4+pinia跨端后台管理系统应用

0 回答

HTML5 Drag与Drop 拖动时更改图标/光标

5 回答

如何完全卸载 Node.js，然后从头重新安装 (Mac OS X)

25 回答

基于tauri+vue3跨端聊天应用|tauri仿微信模板

0 回答

Ace Editor一款比较好用的展示代码组件