从N个数组中选取唯一元素创建大小为N的数组的算法复杂度

Question

存在二维数组A[n][m]，其中n = 2*m.

每个数组A[i]包含[0;n)中的m唯一整数。注意，如果i != j,A[i]和A[j]中的元素可以相交。每个数组A[i]被排序。

:构造包含唯一元素的数组B[n]，从A的每个数组中只取一个元素。如果B[n]不能构建，则没有解决方案。

的例子:

A[0] = {0, 2}
A[1] = {1, 2}
A[2] = {0, 3}
A[3] = {0, 3}
Result: 
Take A[0][1], A[1][0], A[2][0], A[3][1] => B = {2, 1, 0, 3}

我有一个递归算法来解决这个任务:

// level = 0 at first call
fn recursive_choice(a: &mut Vec<Vec<usize>>, b: &mut Vec<usize>, level: usize) {
if level >= a.len() {
return;
}
for idx in 0..a[level].len() {
if !b.contains(&a[level][idx]) {
b.push(a[level][idx]);
recursive_choice(a, b, level + 1);
if a.len() == b.len() {
return;
} else {
b.pop();
}
}
}
}

有没有更好的算法——是什么?在最坏情况下这个算法的复杂度是多少?

Answer 1

这可以看作是在数组和值之间寻找最大匹配的问题。如果匹配包含所有数组，那么您就得到了答案。如果不是，那么答案是否定的。

可以用标准的方法求解，如时间为O(n^4)的Blossom算法。如果您愿意使用更复杂和优化的算法，您可以将其减少到O(n^3)。