如何计算 JavaScript 中多个数组的交集？[equals: function] 是什么意思？

IT技术 javascript arrays
2021-02-07 01:38:58

我知道这个问题，最简单的数组交集代码，但所有的解决方案都假设数组的数量是两个，这在我的情况下是不确定的。

我在包含数组的数据的页面上有 div。我想找到所有数组共有的值。我不知道我会提前有多少个 div/arrays。计算所有数组共有的值的最佳方法是什么？

var array1 = ["Lorem", "ipsum", "dolor"];
var array2 = ["Lorem", "ipsum", "quick", "brown", "foo"];
var array3 = ["Jumps", "Over", "Lazy", "Lorem"];
var array4 = [1337, 420, 666, "Lorem"];
//Result should be ["Lorem"];

我在别处找到了另一个解决方案，使用 Underscore.js。

var arrayOfArrays = [[4234, 2323, 43], [1323, 43, 1313], [23, 34, 43]];
_.intersection.apply(_, arrayOfArrays)
//Result is [43]

我最后用简单的虚拟数据对此进行了测试，它似乎有效。但出于某种原因，我正在生成的一些包含简单字符串的数组也会自动包含一个附加值，“equals: function”：

["Dummy1", "Dummy2", "Dummy3", equals: function]

每当我使用 Underscore.js 交集方法时，在数组数组上，我总是在开发工具中得到 [equals: function]，而不是 - 如果“Dummy3”对所有数组都是通用的 - [“Dummy3”]。

所以 TL;DR 是否有另一种适合我的情况的阵列交集解决方案？谁能解释一下 [equals: function] 在这里的含义？当我在开发工具中展开项目时，它会生成一个空数组和数组上可用的方法列表（pop、push、shift 等），但这些方法都淡出，而 equals: function 突出显示。

6个回答

你可以只使用Array#reduce与Array#filter和Array#includes。

var array1 = ["Lorem", "ipsum", "dolor"],
    array2 = ["Lorem", "ipsum", "quick", "brown", "foo"],
    array3 = ["Jumps", "Over", "Lazy", "Lorem"],
    array4 = [1337, 420, 666, "Lorem"],
    data = [array1, array2, array3, array4],
    result = data.reduce((a, b) => a.filter(c => b.includes(c)));

console.log(result);

我认为O(n * log n)是正确的。我认为可以进一步优化此解决方案的一件事是首先找到最短的数组并将其移动到数据数组的第一个索引。在 reduce 函数中，我们使用 data 中的第一个元素作为起点，然后检查该数组中的每个元素。如果该初始数组尽可能短，则删除额外的迭代。例如，假设我们的数据数组如下所示： [[1, 2, 3, .... , 10000], [1]] 交换这两个元素的顺序会产生很大的不同。很好的解决方案，@NinaScholz！
2021-03-22 01:38:58
@ReactingToAngularVues，它不是二次方的，因为每个循环的零件结果可能会变短。
2021-03-25 01:38:58
@Nathan：绝对不是 O(n log n)。
2021-04-01 01:38:58
对于第一个列表之后的 n 个总元素和 m 个最终元素，它是 Ω(mn)，这与典型的偶然二次事物是同一种性能陷阱。使用Set.
2021-04-06 01:38:58
这个函数的数学复杂度是多少？看起来至少是 O(n²)。
2021-04-09 01:38:58

我为此编写了一个辅助函数：

function intersection() {
  var result = [];
  var lists;

  if(arguments.length === 1) {
    lists = arguments[0];
  } else {
    lists = arguments;
  }

  for(var i = 0; i < lists.length; i++) {
    var currentList = lists[i];
    for(var y = 0; y < currentList.length; y++) {
        var currentValue = currentList[y];
      if(result.indexOf(currentValue) === -1) {
        var existsInAll = true;
        for(var x = 0; x < lists.length; x++) {
          if(lists[x].indexOf(currentValue) === -1) {
            existsInAll = false;
            break;
          }
        }
        if(existsInAll) {
          result.push(currentValue);
        }
      }
    }
  }
  return result;
}

像这样使用它：

intersection(array1, array2, array3, array4); //["Lorem"]

或者像这样：

intersection([array1, array2, array3, array4]); //["Lorem"]

完整代码在这里

更新 1

这里使用稍微小一点的实现filter

谢谢你。我可以遵循它，它可以与虚拟数据 buuuut 一起使用...我没有将单独的数组存储在数组 1、数组 2 和数组 3 等变量中，因为我事先不知道页面上有多少个 div。目前我必须遍历它们并将它们推入另一个容器数组。所以我只能做不能与你的代码一起工作的交集（arrayContainingArrays）。也就是说，这是其他人可以使用的 vanilla JavaScript 的一个很好的解决方案。
2021-03-17 01:38:58
这非常适用于虚拟数组，但不适用于我想要的特定数组。这意味着我最后还缺少其他东西。但是这个答案是一个很好的解决方案，它完全回答了我的问题并且对其他人有用。所以你今天赢得了互联网。
2021-03-20 01:38:58
:O 好的！给我 5 分钟，我会试试这个
2021-03-27 01:38:58
@NN796 应该是空的。所有数组中都不存在任何值。
2021-04-06 01:38:58
与数据集： var array1 = [786, 796] var array2 = [100]; var array3 = [1]; var array4 = [2,3,4,1]; 输出是一个空数组，但它应该是常见的值。请纠正我。谢谢你。
2021-04-14 01:38:58

如果您喜欢使用一些递归和新的 ES2015 语法，这可以非常简洁地完成：

const array1 = ["Lorem", "ipsum", "dolor"];
const array2 = ["Lorem", "ipsum", "quick", "brown", "foo"];
const array3 = ["Jumps", "Over", "Lazy", "Lorem"];
const array4 = [1337, 420, 666, "Lorem"];

const arrayOfArrays = [[4234, 2323, 43], [1323, 43, 1313], [23, 34, 43]];

// Filter xs where, for a given x, there exists some y in ys where y === x.
const intersect2 = (xs,ys) => xs.filter(x => ys.some(y => y === x));

// When there is only one array left, return it (the termination condition
// of the recursion). Otherwise first find the intersection of the first
// two arrays (intersect2), then repeat the whole process for that result
// combined with the remaining arrays (intersect). Thus the number of arrays
// passed as arguments to intersect is reduced by one each time, until
// there is only one array remaining.
const intersect = (xs,ys,...rest) => ys === undefined ? xs : intersect(intersect2(xs,ys),...rest);

console.log(intersect(array1, array2, array3, array4));
console.log(intersect(...arrayOfArrays));

// Alternatively, in old money,

var intersect2ES5 = function (xs, ys) {
    return xs.filter(function (x) {
        return ys.some(function (y) {
            return y === x;
        });
    });
};
    
// Changed slightly from above, to take a single array of arrays,
// which matches the underscore.js approach in the Q., and is better anyhow.
var intersectES5 = function (zss) {
    var xs = zss[0];
    var ys = zss[1];
    var rest = zss.slice(2);
    if (ys === undefined) {
        return xs;
    }
    return intersectES5([intersect2ES5(xs, ys)].concat(rest));
};

console.log(intersectES5([array1, array2, array3, array4]));
console.log(intersectES5(arrayOfArrays));

哼。从来没有遇到过 const 或 rest 。在我的雇主用机器人取代我之前，我最好先阅读 ECMAScript 6 :o
2021-04-09 01:38:58

结合几个贡献者的想法和最新的 ES6 优点，我得到了

const array1 = ["Lorem", "ipsum", "dolor"];
const array2 = ["Lorem", "ipsum", "quick", "brown", "foo"];
const array3 = ["Jumps", "Over", "Lazy", "Lorem"];
const array4 = [1337, 420, 666, "Lorem"];

Array.prototype.intersect = function intersect(a, ...b) {
    const c = function (a, b) {
        b = new Set(b);
        return a.filter((a) => b.has(a));
    };
    return undefined === a ? this : intersect.call(c(this, a), ...b);
};

console.log(array1.intersect(array2, array3, array4));
// ["Lorem"]

不像不创建 那样低效Set，但仍然 1) 扩展原型，除了不好的做法之外，还会创建奇怪的不对称 2)c无缘无故地涉及内部函数3) 通过递归减慢自身速度
2021-03-18 01:38:58

对于未来对此感到困惑的任何人， 

_.intersection.apply(_, arrayOfArrays)

实际上是最优雅的方式来做到这一点。但：

var arrayOfArrays = [[43, 34343, 23232], [43, 314159, 343], [43, 243]];
arrayOfArrays = _.intersection.apply(_, arrayOfArrays);

不管用！必须做

var differentVariableName = _.intersection.apply(_,arrayOfArrays);
其它你可能感兴趣的问题
上一篇来自 XMLHttpRequest 的空响应文本 下一篇跨域 iframe 调整器？