从n个数组构造唯一元素数组的算法复杂度及优化问询

给定二维数组A[n][m]（满足n=2*m），每个子数组A[i]包含m个属于[0,n)的唯一整数，且A[i]已排序，不同子数组元素可重叠。需要构造数组B[n]，要求从每个A[i]中取一个元素，且B中所有元素唯一；若无法构造则判定无解。

示例：

A[0] = {0, 2}
A[1] = {1, 2}
A[2] = {0, 3}
A[3] = {0, 3}

构造结果：取A[0][1], A[1][0], A[2][0], A[3][1]，得到B = {2, 1, 0, 3}

用户实现的递归Rust算法：

// 首次调用时level = 0
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();
            }
        }
    }
}

请问：

1. 是否存在更优的算法？
2. 该递归算法的最坏时间复杂度是多少？

更优算法方案 #

这个问题其实就是二分图匹配问题，用匈牙利算法或者Hopcroft-Karp算法来解效率会高很多，比暴力递归强不止一个档次。

具体建模方式：

• 左侧节点：对应每个子数组A[i]，共n个；
• 右侧节点：对应0到n-1这些元素值，共n个；
• 边：如果元素x存在于A[i]中，就在A[i]对应的左节点和x对应的右节点之间连一条边。

我们要找的是一个大小为n的匹配——每个左节点对应唯一的右节点，这正好满足题目要求的B数组构造条件：每个子数组选一个唯一的元素。

其中Hopcroft-Karp算法的时间复杂度为O(E√V)，这里E是总边数（最多n*m=2m²），V是节点总数（2n），不管n多大，运行效率都比暴力递归高得多，尤其是n较大时，暴力递归根本跑不动，而二分图匹配算法能轻松处理。

至于贪心算法，虽然实现简单，但没法保证所有情况都能找到解，遇到一些特殊构造的数组就会失效，而二分图匹配能准确找到解或者判定无解。

递归算法的最坏时间复杂度分析 #

你写的这个递归属于暴力回溯，最坏情况的时间复杂度是O(n*mⁿ)：

• 一共要处理n个子数组，对应n层递归；
• 每个子数组最多有m个元素可选，最坏情况下每一步都得把m个选项全试一遍（比如所有子数组的元素完全相同，每次都要遍历完所有选项才发现冲突）；
• 另外，b.contains(&x)是线性扫描数组b的操作，时间复杂度为O(n)，所以总的最坏时间复杂度就是O(n*mⁿ)。

举个例子，当n=4、m=2时，最坏情况要尝试2^4=16次，每次还要做O(4)的查找；要是n=10、m=5，那就是5^10=976万+次操作，完全没法实用。

内容的提问来源于stack exchange，提问作者TupleCats