从n个数组中每个数组最多选1个元素，找出m个元素。 (Title)

Question

我有n个数组，每个数组都包含任意数量的整数。数组内不可能有重复项（例如[1,1,2]不能是n个数组之一）。

我还有一个大小为m的整数数组，其中填充了从1到m的整数（数组条目的值=数组索引+1）。例如：m = 4，则适当的数组为[1,2,3,4]。

我的问题是：对于给定的n和m，是否可以通过从每个n个数组中最多选择1个元素来找到m数组中的每个元素？

举个例子：n = 3，m = 3，n个数组分别是[1]、[1,2]和[2,3]。输出应该是Yes，因为我们可以从n个数组中选择1个元素，从第一个数组中选择1，从第二个数组中选择2，从第三个数组中选择3，这样就能找到m数组中的每个元素。

这是一个面试题，我得到了一个提示，要考虑最大流问题（但我不知道这如何帮助我）。

- PlsWork

---

能够出现 n = [5,7] [8,9] [10,15] ... m = [1,2,3,4] 吗？或者说有没有条件不允许 n 和 m 数组如此不同？如果我没记错的话，最大流算法与图形有关，因此 n 数组可能是一个节点。你只需从那里选择一条边即可到达目的地。 - hamena314

那么关于问题的编程方面呢？也许你写了一些代码来帮助你解决它了吗？ - ShayHaned

@hamena314 可能存在这样的 n 个数组。 - PlsWork

@ShayHaned 当我甚至无法在纸上想出问题的一般解决方案时，编写代码就变得困难了。 - PlsWork

Answer 1

你可以像这样构建一个图表：图表被分成左侧和右侧两部分。左侧包含 n 个顶点，代表 n 个数组。右侧包含 m 个顶点，代表 m 个数字。

然后我们考虑这些n个数组。如果元素k包含在第i个数组中，我们就在从左侧数第i个顶点和从右侧数第k个顶点之间绘制一条边。我们的目标是选择m条边，以便右侧的m个顶点恰好被m条边覆盖，并且左侧的顶点最多被覆盖一次。这是一个二分图最大匹配问题，可以通过许多算法解决，包括最大流。

- TsReaper

---

有趣的方法，在纸上看起来可行，我会尝试实现它。 - PlsWork

已添加一张图片 - 如果我弄错了，请告诉我。 - slim

Answer 2

我认为可以使用递归方法来实现。

• 如果m是一个空列表，则PASS
• 否则，查找包含m的第一个元素的成员
  • 如果没有找到：FAIL
  • 对于每个找到的：
    • 如果存在m'=tail(m)和n'=（n）的其他成员的PASS，则m的这个成员是PASS的一部分

我还没有测试过，但：

public boolean check(List<Integer> m, List<List<Integer>> n) {
    if (m.isEmpty()) {
        return true;
    }

    int head = head(m);
    List<Integer> tail = tail(m);

    for (List<Integer> nMember : n) {
        if (nMember.contains(head) && check(tail, nMinus(n, nMember))) {
            return true;
        }
    }

    return false;

}

假设的方法：

• head() 返回传递列表的第一个元素。
• tail() 返回已删除第一个元素的传递列表。
• nMinus() 返回已删除nMember的n的视图或副本。 它不应修改n。

您应该使用不可变集合，或者至少将它们视为不可变。 Guava提供的类可能会很有用。 但是，您可以非常轻松地创建一个ListOmitting列表包装器类，以实现nMinus()而无需使用Guava。

我不能确定它是否过于暴力，但对于面试答案来说，它“感觉”足够高效。

- slim

---

请注意，尽管这是一个有效的解决方案，但它需要指数时间。添加一种高级解释方法可能是个好主意。 - Bernhard Barker

这种方法效率太低。 - PlsWork