用javascript实现数组交叉的最简单、无库代码是什么?我想写

intersection([1,2,3], [2,3,4,5])

并获得

[2, 3]

当前回答

该函数利用字典的强大功能,避免了N^2问题。每个数组只循环一次,第三次更短的循环返回最终结果。 它还支持数字、字符串和对象。

function array_intersect(array1, array2) 
{
    var mergedElems = {},
        result = [];

    // Returns a unique reference string for the type and value of the element
    function generateStrKey(elem) {
        var typeOfElem = typeof elem;
        if (typeOfElem === 'object') {
            typeOfElem += Object.prototype.toString.call(elem);
        }
        return [typeOfElem, elem.toString(), JSON.stringify(elem)].join('__');
    }

    array1.forEach(function(elem) {
        var key = generateStrKey(elem);
        if (!(key in mergedElems)) {
            mergedElems[key] = {elem: elem, inArray2: false};
        }
    });

    array2.forEach(function(elem) {
        var key = generateStrKey(elem);
        if (key in mergedElems) {
            mergedElems[key].inArray2 = true;
        }
    });

    Object.values(mergedElems).forEach(function(elem) {
        if (elem.inArray2) {
            result.push(elem.elem);
        }
    });

    return result;
}

如果有无法解决的特殊情况,仅通过修改generateStrKey函数就可以解决。这个函数的诀窍在于,它根据类型和值唯一地表示每个不同的数据。


这个变体有一些性能改进。在任何数组为空的情况下避免循环。它还首先遍历较短的数组,因此如果它在第二个数组中找到了第一个数组的所有值,则退出循环。

function array_intersect(array1, array2) 
{
    var mergedElems = {},
        result = [],
        firstArray, secondArray,
        firstN = 0, 
        secondN = 0;

    function generateStrKey(elem) {
        var typeOfElem = typeof elem;
        if (typeOfElem === 'object') {
            typeOfElem += Object.prototype.toString.call(elem);
        }
        return [typeOfElem, elem.toString(), JSON.stringify(elem)].join('__');
    }

    // Executes the loops only if both arrays have values
    if (array1.length && array2.length) 
    {
        // Begins with the shortest array to optimize the algorithm
        if (array1.length < array2.length) {
            firstArray = array1;
            secondArray = array2;
        } else {
            firstArray = array2;
            secondArray = array1;            
        }

        firstArray.forEach(function(elem) {
            var key = generateStrKey(elem);
            if (!(key in mergedElems)) {
                mergedElems[key] = {elem: elem, inArray2: false};
                // Increases the counter of unique values in the first array
                firstN++;
            }
        });

        secondArray.some(function(elem) {
            var key = generateStrKey(elem);
            if (key in mergedElems) {
                if (!mergedElems[key].inArray2) {
                    mergedElems[key].inArray2 = true;
                    // Increases the counter of matches
                    secondN++;
                    // If all elements of first array have coincidence, then exits the loop
                    return (secondN === firstN);
                }
            }
        });

        Object.values(mergedElems).forEach(function(elem) {
            if (elem.inArray2) {
                result.push(elem.elem);
            }
        });
    }

    return result;
}

其他回答

function intersectionOfArrays(arr1, arr2) {
    return arr1.filter((element) => arr2.indexOf(element) !== -1).filter((element, pos, self) => self.indexOf(element) == pos);
}

使用一个数组创建一个Object,并循环遍历第二个数组以检查该值是否作为key存在。

function intersection(arr1, arr2) {
  var myObj = {};
  var myArr = [];
  for (var i = 0, len = arr1.length; i < len; i += 1) {
    if(myObj[arr1[i]]) {
      myObj[arr1[i]] += 1; 
    } else {
      myObj[arr1[i]] = 1;
    }
  }
  for (var j = 0, len = arr2.length; j < len; j += 1) {
    if(myObj[arr2[j]] && myArr.indexOf(arr2[j]) === -1) {
      myArr.push(arr2[j]);
    }
  }
  return myArr;
}

下面是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

我写了一个相交函数,它甚至可以根据对象的特定属性来检测对象数组的交集。

例如,

if arr1 = [{id: 10}, {id: 20}]
and arr2 =  [{id: 20}, {id: 25}]

我们想要基于id属性的交集,那么输出应该是:

[{id: 20}]

因此,相同(注:ES6代码)的函数为:

const intersect = (arr1, arr2, accessors = [v => v, v => v]) => {
    const [fn1, fn2] = accessors;
    const set = new Set(arr2.map(v => fn2(v)));
    return arr1.filter(value => set.has(fn1(value)));
};

你可以这样调用这个函数:

intersect(arr1, arr2, [elem => elem.id, elem => elem.id])

还要注意:该函数查找交集时考虑到第一个数组是主数组,因此交集结果将是主数组的结果。

简单性:

// 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引擎或内核工作,但如果你在基于事件的应用程序中运行时遇到问题,那么你的设计就有更大的问题。