Javascript获取三个数组的共同元素

Question

我正在尝试过滤 3 个数组的公共元素。但是它不是获取 3 个数组的公共元素，而是只读取 2 个数组而不是第 3 个数组。这是我的代码，谢谢：

function commonElementsOfArray(arr1, arr2, arr3) {
    return arr1.filter(function (n) {
        return arr2.indexOf(n) !== -1;
        return arr3.indexOf(n) !== -1;
    });
}

Answer 1

如何将 OP 代码重构为通用相交功能，该功能实现两个数组的简化相交功能，并通过处理通用函数（数组）的 reduce 任务生成 2 个以上数组的整体交集类型）参数？

因此，两个数组的交集将基于 OP 的代码 filter approach but using includes instead of indexOf。像...

function getIntersectionOfTwo(a, b) {
  return a.filter(function (n) {
    return b.includes(n);
  });
}

泛型 getIntersection 然后只需要确保其参数的类型安全和正确的 return 参数太少的值以及正确提供的参数的最小数量的交集结果...

function getIntersection(...listOfArrays) {
  function getIntersectionOfTwo(a, b) {
    return a.filter(function (n) {
      return b.includes(n);
    });
  }
  // assure only array type arguments.
  listOfArrays = listOfArrays.filter(Array.isArray);

  return (listOfArrays[1] ?? listOfArrays[0])
    && listOfArrays.reduce(getIntersectionOfTwo);   
}

console.log(
  'getIntersection() ...',
  getIntersection()
);
console.log(
  'getIntersection(9, "foo", 0) ...',
  getIntersection(9, "foo", 0)
);
console.log(
  'getIntersection([2, 7, 0], "bar") ...',
  getIntersection([2, 7, 0], "bar")
);
console.log(
  'getIntersection([2, 7, 0, 4], [6, 2, 7, 3]) ...',
  getIntersection([2, 7, 0, 4], [6, 2, 7, 3])
);
console.log(
  'getIntersection([2, 7, 0, 4], [6, 2, 7, 3], [9, 1, 2]) ...',
  getIntersection([2, 7, 0, 4], [6, 2, 7, 3], [9, 1, 2])
);
console.log(
  'getIntersection([2, 7, 0, 4], [6, 2, 7, 3], [9]) ...',
  getIntersection([2, 7, 0, 4], [6, 2, 7, 3], [9])
);

.as-console-wrapper { min-height: 100%!important; top: 0; }

以上示例对 getIntersectionOfTwo of cause 的实现保持简单，以便更好地理解整个任务的重构过程。

在下一个重构步骤中，也可以改进此功能，以便更有效地 handle/process 大量数组数据。因此，人们会在 filter 回调中使用基于 Map 的查找，而不是在每个 filter 迭代中搜索是否 b.includes(n).

function getIntersection(...listOfArrays) {
  function getIntersectionOfTwo(intersection, iterableItem) {
    // in order to compare huge arrays more efficiently access ...
    const [

      comparisonBase, // ... the shorter one as comparison base
      comparisonList, // ... and the longer one to filter from.

    ] = [intersection, iterableItem]
      .sort((a, b) => a.length - b.length);

    // create a `Map` based lookup table from the shorter array.
    const itemLookup = comparisonBase
      .reduce((map, item) => map.set(item, true), new Map)

    // the intersection is the result of following filter task.
    return comparisonList.filter(item => itemLookup.has(item));
  }
  // assure only array type arguments.
  listOfArrays = listOfArrays.filter(Array.isArray);

  return (listOfArrays[1] ?? listOfArrays[0])
    && listOfArrays.reduce(getIntersectionOfTwo);   
}

console.log(
  'getIntersection() ...',
  getIntersection()
);
console.log(
  'getIntersection(9, "foo", 0) ...',
  getIntersection(9, "foo", 0)
);
console.log(
  'getIntersection([2, 7, 0], "bar") ...',
  getIntersection([2, 7, 0], "bar")
);
console.log(
  'getIntersection([2, 7, 0, 4], [6, 2, 7, 3]) ...',
  getIntersection([2, 7, 0, 4], [6, 2, 7, 3])
);
console.log(
  'getIntersection([2, 7, 0, 4], [6, 2, 7, 3], [9, 1, 2]) ...',
  getIntersection([2, 7, 0, 4], [6, 2, 7, 3], [9, 1, 2])
);
console.log(
  'getIntersection([2, 7, 0, 4], [6, 2, 7, 3], [9]) ...',
  getIntersection([2, 7, 0, 4], [6, 2, 7, 3], [9])
);

.as-console-wrapper { min-height: 100%!important; top: 0; }

Answer 2

如@Titus 所述，您的代码中的问题是双 return 语句 - 一旦找到第一个 return，过滤函数将退出。

但是，在您寻找关于 Array.indexOf 的共同元素的方法中，还有一个值得指出的问题。问题是 Array.indexOf 是一个 O(n) 操作，这意味着将针对 arr2 的每个元素和 arr3 的每个元素检查参数。从表面上看，这听起来像是正确的方法，但如果数组很大，那么这将是一个非常慢的函数。例如，如果每个数组有 1,000 个条目 (n)，那么您的函数将获取每个元素并与 arr2 和 arr3 (n) 中的所有元素进行比较。导致 O(n^2) 时间复杂度。

一种替代方法是创建一个 Map 并在遍历每个数组时填充它以跟踪条目被看到的次数。查找值现在有 O(1) 运行时间。迭代每个数组的成本仍然是 O(n)，但由于快速查找，这变成了 n * 1 操作或 O(n) 时间复杂度。

function commonElementsOfArray(arr1, arr2, arr3) {
  const map = new Map();
  const updateMap = arr => {
    arr.forEach(entry => {
      if (!map.has(entry)) {
        map.set(entry, 1);
      } else {
        let timesSeen = map.get(entry);
        map.set(entry, ++timesSeen);
      }
    });
  };

  updateMap(arr1);
  updateMap(arr2);
  updateMap(arr3);

  map.forEach((count, key) => {
    // remove all entries not seen at least 3 times
    if (count !== 3) {
      map.delete(key);
    }
  });

  return [...map.keys()];
}

console.log(commonElementsOfArray([1, 2, 3], [1, 2, 4], [2, 4, 5]));

Javascript获取三个数组的共同元素

Javascript Get the common elements of three arrays

javascript

arrays

intersection