Javascript javascript中数组交集的最简单代码
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1885557/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Simplest code for array intersection in javascript
提问by Peter
What's the simplest, library-free code for implementing array intersections in javascript? I want to write
在 javascript 中实现数组交集的最简单、无库的代码是什么？我想写
intersection([1,2,3], [2,3,4,5])
and get
并得到
[2, 3]
回答by Anon.
Use a combination of Array.prototype.filterand Array.prototype.indexOf:
使用的组合Array.prototype.filter和Array.prototype.indexOf：
array1.filter(value => -1 !== array2.indexOf(value))
Or as vrugtehagelsuggested in the comments, you can use the more recent Array.prototype.includesfor even simpler code:
或者正如vrugtehagel在评论中建议的那样，您可以使用更新Array.prototype.includes的代码来获得更简单的代码：
array1.filter(value => array2.includes(value))
For older browsers:
对于旧浏览器：
array1.filter(function(n) {
return array2.indexOf(n) !== -1;
});
回答by atk
Destructive seems simplest, especially if we can assume the input is sorted:
破坏性似乎最简单，特别是如果我们可以假设输入已排序：
/* 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;
}
Non-destructive has to be a hair more complicated, since we've got to track indices:
非破坏性必须更复杂，因为我们必须跟踪索引：
/* 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;
}
回答by nbarbosa
If your environment supports ECMAScript 6 Set, one simple and supposedly efficient (see specification link) way:
如果您的环境支持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);
}
Shorter, but less readable (also without creating the additional intersection Set):
更短，但可读性较差（也不创建额外的交叉点Set）：
function intersect(a, b) {
return [...new Set(a)].filter(x => new Set(b).has(x));
}
Avoiding a new Setfrom bevery time:
避免新Set的b每次：
function intersect(a, b) {
var setB = new Set(b);
return [...new Set(a)].filter(x => setB.has(x));
}
Note that when using sets you will only get distinct values, thus new Set[1,2,3,3].sizeevaluates to 3.
请注意，使用集合时，您只会得到不同的值，因此new Set[1,2,3,3].size计算结果为3。
回答by Sai Ram
Using Underscore.jsor lodash.js
使用 Underscore.js或lodash.js
_.intersection( [0,345,324] , [1,0,324] ) // gives [0,324]
回答by Redu
My contribution in ES6 terms. In general it finds the intersection of an array with indefinite number of arrays provided as arguments.
我在 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>");回答by le_m
// 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]));I recommend above succinct solution which outperforms other implementations on large inputs. If performance on small inputs matters, check the alternatives below.
我推荐上述简洁的解决方案，它在大输入上优于其他实现。如果小输入的性能很重要，请检查下面的替代方案。
Alternatives and performance comparison:
替代方案和性能比较：
See the following snippet for alternative implementations and check https://jsperf.com/array-intersection-comparisonfor performance comparisons.
有关替代实现，请参阅以下代码段，并检查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;
}Results in Firefox 53:
Firefox 53 中的结果：
Ops/sec on large arrays (10,000 elements):
filter + has (this) 523 (this answer) for + has 482 for-loop + in 279 filter + in 242 for-loops 24 filter + includes 14 filter + indexOf 10Ops/sec on small arrays (100 elements):
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
大型阵列（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
回答by Steven Huwig
How about just using associative arrays?
只使用关联数组怎么样？
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;
}
edit:
编辑：
// 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;
}
回答by YOU
- Sort it
- check one by one from the index 0, create new array from that.
- 把它分类
- 从索引 0 中一一检查，从中创建新数组。
Something like this, Not tested well though.
像这样的东西，虽然没有经过很好的测试。
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:The algorithm only intended for Numbers and Normal Strings, intersection of arbitary object arrays may not work.
PS：该算法仅适用于数字和普通字符串，任意对象数组的交集可能不起作用。
回答by xn.
The performance of @atk's implementation for sorted arrays of primitives can be improved by using .pop rather than .shift.
使用 .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;
}
I created a benchmark using jsPerf: http://bit.ly/P9FrZK. It's about three times faster to use .pop.
我使用 jsPerf 创建了一个基准测试：http://bit.ly/P9FrZK 。使用 .pop 大约快三倍。
回答by Gowsikan
Using jQuery:
使用jQuery：
var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);
