用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
当前回答
与效率无关,但很容易理解,这里有一个集合的并和交的例子,它处理集合的数组和集合的集合。
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;
}
当然,你需要确保这个键之前没有出现过,否则你会破坏你的数据…
对于只包含字符串或数字的数组,你可以做一些排序,就像其他答案一样。对于任意对象数组的一般情况,我不认为你可以避免这样做。下面将为您提供任意数量的数组的交集作为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"];
下面是underscore.js的实现:
_.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;
};
来源:http://underscorejs.org/docs/underscore.html部分- 62
解决它 从索引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:该算法仅适用于数字和普通字符串,任意对象数组的交集可能无法工作。
对这里最小的一个(filter/indexOf解决方案)稍作调整,即使用JavaScript对象在其中一个数组中创建值的索引,将从O(N*M)减少到“可能”线性时间。source1 source2
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()慢一个常数因子),但似乎是一个很好的平衡。它非常简单,同时提供了良好的性能,并且不需要预先排序的输入。