用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
用javascript实现数组交叉的最简单、无库代码是什么?我想写
intersection([1,2,3], [2,3,4,5])
并获得
[2, 3]
当前回答
下面是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
其他回答
另一种可以同时处理任意数量数组的索引方法:
// Calculate intersection of multiple array or object values.
function intersect (arrList) {
var arrLength = Object.keys(arrList).length;
// (Also accepts regular objects as input)
var index = {};
for (var i in arrList) {
for (var j in arrList[i]) {
var v = arrList[i][j];
if (index[v] === undefined) index[v] = 0;
index[v]++;
};
};
var retv = [];
for (var i in index) {
if (index[i] == arrLength) retv.push(i);
};
return retv;
};
它只适用于可以作为字符串计算的值,你应该将它们作为一个数组传递:
intersect ([arr1, arr2, arr3...]);
...但它透明地接受对象作为参数或任何要交叉的元素(总是返回公共值的数组)。例子:
intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4]
intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"]
编辑:我只是注意到,这是,在某种程度上,有点bug。
也就是说:我在编码时认为输入数组本身不能包含重复(正如所提供的示例那样)。
但如果输入数组恰好包含重复,就会产生错误的结果。示例(使用下面的实现):
intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]);
// Expected: [ '1' ]
// Actual: [ '1', '3' ]
幸运的是,这很容易通过添加二级索引来解决。那就是:
变化:
if (index[v] === undefined) index[v] = 0;
index[v]++;
by:
if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.
,:
if (index[i] == arrLength) retv.push(i);
by:
if (Object.keys(index[i]).length == arrLength) retv.push(i);
完整的例子:
// Calculate intersection of multiple array or object values.
function intersect (arrList) {
var arrLength = Object.keys(arrList).length;
// (Also accepts regular objects as input)
var index = {};
for (var i in arrList) {
for (var j in arrList[i]) {
var v = arrList[i][j];
if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.
};
};
var retv = [];
for (var i in index) {
if (Object.keys(index[i]).length == arrLength) retv.push(i);
};
return retv;
};
intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // [ '1' ]
如果你需要让它处理交叉多个数组:
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]))
通过对数据的一些限制,您可以在线性时间内完成!
对于正整数:使用一个数组将值映射到“已见/未见”布尔值。
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;
}
当然,你需要确保这个键之前没有出现过,否则你会破坏你的数据…
“filter”和“indexOf”在IE中的Array上不支持。这个怎么样:
var array1 = [1, 2, 3];
var array2 = [2, 3, 4, 5];
var intersection = [];
for (i in array1) {
for (j in array2) {
if (array1[i] == array2[j]) intersection.push(array1[i]);
}
}
解决它 从索引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:该算法仅适用于数字和普通字符串,任意对象数组的交集可能无法工作。