JavaScript中寻找包含其他各数组至少一个元素的最小子数组的最简方法？

嘿，这个问题其实可以用贪心算法来高效解决，而且实现起来也挺简洁的。先明确需求：我们要找一个最小的数组，它得包含每个输入子数组里的至少一个元素——就像你举的例子，[1,4]里的1覆盖了前两个数组，4覆盖了第三个数组，完美符合要求。

核心思路 #

这本质上是经典的集合覆盖问题：我们需要用最少的元素（每个元素对应它能覆盖的输入子数组集合），覆盖所有输入子数组。对于日常开发中的小规模场景，贪心算法是个简单又实用的选择——每次选能覆盖最多未被覆盖子数组的元素，直到所有子数组都被覆盖。

代码实现 #

function findMinCoveringSubarray(arrays) {
  // 记录每个元素能覆盖的输入子数组索引集合
  const elementCoverage = {};
  arrays.forEach((arr, index) => {
    arr.forEach(num => {
      if (!elementCoverage[num]) {
        elementCoverage[num] = new Set();
      }
      elementCoverage[num].add(index);
    });
  });

  // 所有需要覆盖的子数组索引
  const totalIndices = new Set(Array.from({ length: arrays.length }, (_, i) => i));
  const selectedElements = [];
  const coveredIndices = new Set();

  // 循环直到覆盖所有子数组
  while (coveredIndices.size < totalIndices.size) {
    let bestElement = null;
    let maxNewCoverage = 0;

    // 找出当前能覆盖最多未被覆盖子数组的元素
    Object.entries(elementCoverage).forEach(([num, indices]) => {
      const newUncovered = Array.from(indices).filter(idx => !coveredIndices.has(idx)).length;
      if (newUncovered > maxNewCoverage) {
        maxNewCoverage = newUncovered;
        bestElement = Number(num);
      }
    });

    // 处理无解情况（题目应该保证有解，这里做个兜底）
    if (!bestElement) break;

    // 选中该元素，更新覆盖状态
    selectedElements.push(bestElement);
    elementCoverage[bestElement].forEach(idx => coveredIndices.add(idx));
    // 移除已选元素，避免重复选择
    delete elementCoverage[bestElement];
  }

  return selectedElements;
}

// 测试你的示例
const inputArrays = [[1,2], [1,3], [4]];
console.log(findMinCoveringSubarray(inputArrays)); // 输出: [1, 4]

代码解释 #

1. 构建覆盖映射：elementCoverage对象会记录每个元素对应的输入子数组索引，比如例子里的1对应Set{0,1}（覆盖第0和第1个子数组），4对应Set{2}。
2. 贪心选择元素：每次循环都找出能覆盖最多未被覆盖子数组的元素，优先选这类元素能最快缩小覆盖范围。
3. 更新覆盖状态：选中元素后，把它覆盖的子数组索引加入已覆盖集合，同时移除这个元素避免重复选择。

补充说明 #

• 如果存在多个最优解（比如输入是[[1,2],[2,3],[1,3]]，那么[1,3]、[2,3]、[1,2]都是最优解），这个算法会返回第一个找到的最优解。
• 集合覆盖是NP难问题，对于超大规模输入，贪心算法只能得到近似最优解，但对于日常开发中的大多数场景，这个实现足够简洁高效。

内容的提问来源于stack exchange，提问作者js_helper