用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
当前回答
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;
}
其他回答
如果您的环境支持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);
}
更短,但可读性更差(也没有创建额外的交集集):
function intersect(a, b) {
var setB = new Set(b);
return [...new Set(a)].filter(x => setB.has(x));
}
注意,当使用Set时,你只会得到不同的值,因此new Set([1,2,3,3])。Size的值为3。
在coffescript中N个数组的交集
getIntersection: (arrays) ->
if not arrays.length
return []
a1 = arrays[0]
for a2 in arrays.slice(1)
a = (val for val in a1 when val in a2)
a1 = a
return a1.unique()
如果你需要让它处理交叉多个数组:
Const intersect = (a1, a2,…rest) => { Const a12 = a1。过滤器(value => a2.includes(value)) 如果休息。长度=== 0){返回a12;} 回归相交(a12,…rest); }; console.log(相交([1、2、3、4、5],[1,2],[1、2、3、4、5],[2 10 1]))
//在线性时间内返回数组a中也在b中的元素: 函数相交(a, b) { 返回a.filter (Set.prototype。new Set(b)); } / /例如: console.log(相交([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 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 10 Ops/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
破坏性似乎是最简单的,特别是如果我们可以假设输入是排序的:
/* 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;
}