java - 通过从 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，是否可以通过从每个元素中选择最多 1 个元素来找到 m 数组中的每个元素n 个数组？

一个例子:

n = 3, m = 3,

n数组:[1], [1, 2], [2, 3]

输出应该是:是

(因为我们可以通过从每个 n 数组中选取最多 1 个元素来找到 m 数组中的每个元素。查看 n 数组并从第一个数组中选择 1，从第二个数组中选择 2，从第三个数组中选择 3。)

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

Answer 1

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

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