通过从 n 个数组中的每个数组中选择最多 1 个元素，在 n 个数组中找到 m 个元素

Question

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

我还有一个大小为 m 的整数数组，其中填充了从 1 到 m 的整数 (value_of_an_array_entry = array_index+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 个元素来找到 m 数组中的每个元素。查看 n 数组并选择 1 来自第一个数组，2 来自第二个数组，3 来自第三个数组。）

这是一道面试题，我得到了一个思考最大流问题的提示（我看不出这对我有什么帮助）。

Answer 1

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

然后我们考虑这些n数组。如果元素 k 包含在第 i 个数组中，我们在从左起第 i 个顶点和从右起第 k 个顶点之间绘制一条边.我们的目标是选择 m 条边，使得右边的每个 m 顶点都被 m 条边恰好覆盖一次，而左边的顶点最多被覆盖一次.这是一个二分图最大匹配问题，可以用很多算法解决，包括max flow

Answer 2

我认为递归方法应该可以做到。

如果m是一个空列表，PASS
否则，寻找包含m的第一个元素的m的成员
- 如果 none 发现：失败
- 每找到一个：
  - 如果 m' = tail(m) 和 n' = other members of (n)

我还没有测试过，但是：

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() returns 传递列表的第一个元素。
tail() returns 删除第一个元素的传递列表。
nMinus() returns n 的视图或副本，删除了 nMember。它不应该修改 n.

您应该使用不可变集合，或者至少将它们视为不可变集合。 Guava 提供了可能有用的 classes。但是你可以很简单地敲出一个 ListOmitting 列表包装器 class 来实现 nMinus() 而不用 Guava。

我不能肯定地说它不是太暴力，但它 "feels" 对于我的采访回答来说足够有效。

通过从 n 个数组中的每个数组中选择最多 1 个元素，在 n 个数组中找到 m 个元素

Find m elements in n arrays by picking at most 1 element out of each of the n arrays

java

arrays

algorithm

max-flow