用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;
}
其他回答
与效率无关,但很容易理解,这里有一个集合的并和交的例子,它处理集合的数组和集合的集合。
http://jsfiddle.net/zhulien/NF68T/
// process array [element, element...], if allow abort ignore the result
function processArray(arr_a, cb_a, blnAllowAbort_a)
{
var arrResult = [];
var blnAborted = false;
var intI = 0;
while ((intI < arr_a.length) && (blnAborted === false))
{
if (blnAllowAbort_a)
{
blnAborted = cb_a(arr_a[intI]);
}
else
{
arrResult[intI] = cb_a(arr_a[intI]);
}
intI++;
}
return arrResult;
}
// process array of operations [operation,arguments...]
function processOperations(arrOperations_a)
{
var arrResult = [];
var fnOperationE;
for(var intI = 0, intR = 0; intI < arrOperations_a.length; intI+=2, intR++)
{
var fnOperation = arrOperations_a[intI+0];
var fnArgs = arrOperations_a[intI+1];
if (fnArgs === undefined)
{
arrResult[intR] = fnOperation();
}
else
{
arrResult[intR] = fnOperation(fnArgs);
}
}
return arrResult;
}
// return whether an element exists in an array
function find(arr_a, varElement_a)
{
var blnResult = false;
processArray(arr_a, function(varToMatch_a)
{
var blnAbort = false;
if (varToMatch_a === varElement_a)
{
blnResult = true;
blnAbort = true;
}
return blnAbort;
}, true);
return blnResult;
}
// return the union of all sets
function union(arr_a)
{
var arrResult = [];
var intI = 0;
processArray(arr_a, function(arrSet_a)
{
processArray(arrSet_a, function(varElement_a)
{
// if the element doesn't exist in our result
if (find(arrResult, varElement_a) === false)
{
// add it
arrResult[intI] = varElement_a;
intI++;
}
});
});
return arrResult;
}
// return the intersection of all sets
function intersection(arr_a)
{
var arrResult = [];
var intI = 0;
// for each set
processArray(arr_a, function(arrSet_a)
{
// every number is a candidate
processArray(arrSet_a, function(varCandidate_a)
{
var blnCandidate = true;
// for each set
processArray(arr_a, function(arrSet_a)
{
// check that the candidate exists
var blnFoundPart = find(arrSet_a, varCandidate_a);
// if the candidate does not exist
if (blnFoundPart === false)
{
// no longer a candidate
blnCandidate = false;
}
});
if (blnCandidate)
{
// if the candidate doesn't exist in our result
if (find(arrResult, varCandidate_a) === false)
{
// add it
arrResult[intI] = varCandidate_a;
intI++;
}
}
});
});
return arrResult;
}
var strOutput = ''
var arrSet1 = [1,2,3];
var arrSet2 = [2,5,6];
var arrSet3 = [7,8,9,2];
// return the union of the sets
strOutput = union([arrSet1, arrSet2, arrSet3]);
alert(strOutput);
// return the intersection of 3 sets
strOutput = intersection([arrSet1, arrSet2, arrSet3]);
alert(strOutput);
// of 3 sets of sets, which set is the intersecting set
strOutput = processOperations([intersection,[[arrSet1, arrSet2], [arrSet2], [arrSet2, arrSet3]]]);
alert(strOutput);
通过对数据的一些限制,您可以在线性时间内完成!
对于正整数:使用一个数组将值映射到“已见/未见”布尔值。
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;
}
当然,你需要确保这个键之前没有出现过,否则你会破坏你的数据…
function intersectionOfArrays(arr1, arr2) {
return arr1.filter((element) => arr2.indexOf(element) !== -1).filter((element, pos, self) => self.indexOf(element) == pos);
}
基于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;
});
});
}
我在ES6方面的贡献。一般来说,它会找到一个数组与作为参数提供的不确定数量的数组的交集。
Array.prototype.intersect = function(…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]; 文档。以前写(“< >”+ JSON.stringify (arr.intersect (arr)) + " < / pre > ");