用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
当前回答
破坏性似乎是最简单的,特别是如果我们可以假设输入是排序的:
/* 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;
}
其他回答
我会用对我来说最有效的方法来贡献:
if (!Array.prototype.intersect){
Array.prototype.intersect = function (arr1) {
var r = [], o = {}, l = this.length, i, v;
for (i = 0; i < l; i++) {
o[this[i]] = true;
}
l = arr1.length;
for (i = 0; i < l; i++) {
v = arr1[i];
if (v in o) {
r.push(v);
}
}
return r;
};
}
基于Anon的出色回答,这个函数返回两个或多个数组的交集。
function arrayIntersect(arrayOfArrays)
{
var arrayCopy = arrayOfArrays.slice(),
baseArray = arrayCopy.pop();
return baseArray.filter(function(item) {
return arrayCopy.every(function(itemList) {
return itemList.indexOf(item) !== -1;
});
});
}
简单性:
// 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引擎或内核工作,但如果你在基于事件的应用程序中运行时遇到问题,那么你的设计就有更大的问题。
对于只包含字符串或数字的数组,你可以做一些排序,就像其他答案一样。对于任意对象数组的一般情况,我不认为你可以避免这样做。下面将为您提供任意数量的数组的交集作为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"];
使用jQuery:
var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);