我有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数组中的每个元素。
这是一个面试题,我得到了一个提示,要考虑最大流问题(但我不知道这如何帮助我)。
我还有一个大小为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数组中的每个元素。
这是一个面试题,我得到了一个提示,要考虑最大流问题(但我不知道这如何帮助我)。
n = [5,7] [8,9] [10,15] ... m = [1,2,3,4]
吗?或者说有没有条件不允许 n 和 m 数组如此不同?如果我没记错的话,最大流算法与图形有关,因此 n 数组可能是一个节点。你只需从那里选择一条边即可到达目的地。 - hamena314n
个数组。 - PlsWork