Rust中合并含重复元素列表的方法及欧拉计划第5题优化问询

问题1：合并列表使B成为A的子集（支持重复元素） #

我想知道在Rust里有没有现成的容器或者方法，可以把元素列表B合并到列表A里，最终让B的所有元素（包括重复项）都成为A的子集？举个具体例子：

• 初始A = {1, 2, 3}
• B = {2, 2, 3}
• 期望结果A = {1, 2, 2, 3}

问题2：欧拉计划第5题的实现优化 #

我现在在解决欧拉计划第5题，目前写了两种实现方案，想问问有没有更合适的Rust集合类型来优化第一种实现？

我的第一种实现代码如下：

fn prime_factors(mut n: i64) -> Vec<i64> {
    let mut factors = Vec::new();
    let mut p = 2;
    while n >= p * p {
        if n % p == 0 {
            factors.push(p);
            n /= p;
        } else {
            p += 1;
        }
    }
    factors.push(n);
    factors
}

pub fn smallest_multiple(n: i64) -> i64 {
    let mut factors: Vec<i64> = Vec::new();
    for p in 1..n + 1 {
        let pfs = prime_factors(p as i64);
        for ele in &pfs {
            let a = pfs.iter().filter(|n| *n == ele).count();
            let b = factors.iter().filter(|n| *n == ele).count();
            let diff = if a > b { a - b } else { continue; };
            for _ in 0..diff {
                factors.push(*ele);
            }
        }
    }
    factors.iter().product()
}

另外我知道这个问题可以用最大公约数（gcd）和最小公倍数（lcm）来解决，实现如下：

pub fn smallest_multiple2(n: u64) -> u64 {
    let mut res: u64 = 1;
    let gcd = |mut a: u64, mut b: u64| -> u64 {
        while a != 0 {
            let c = a;
            a = b % a;
            b = c;
        }
        b
    };
    let lcm = |a: u64, b: u64| -> u64 {
        a * (b / gcd(a, b))
    };
    for i in 2..n + 1 {
        res = lcm(res, i);
    }
    res
}

针对问题1的解答 #

Rust标准库里没有直接做这个操作的现成容器，但我们可以用HashMap（或者有序的BTreeMap）来统计元素出现次数，高效完成合并操作，思路如下：

1. 分别统计列表A和B中每个元素的出现次数
2. 对每个元素，保留A、B中较大的那个计数
3. 根据最终的计数重新生成列表A

给你写个简单的实现示例：

use std::collections::HashMap;

fn merge_lists(a: &mut Vec<i64>, b: &Vec<i64>) {
    // 统计A的元素计数
    let mut count_a: HashMap<&i64, usize> = HashMap::new();
    for num in a.iter() {
        *count_a.entry(num).or_insert(0) += 1;
    }
    // 统计B的元素计数
    let mut count_b: HashMap<&i64, usize> = HashMap::new();
    for num in b.iter() {
        *count_b.entry(num).or_insert(0) += 1;
    }
    // 合并计数，保留最大值
    for (num, &cnt) in count_b.iter() {
        *count_a.entry(num).or_insert(0) = cnt.max(*count_a.get(num).unwrap_or(&0));
    }
    // 重新生成列表A
    a.clear();
    for (&num, &cnt) in count_a.iter() {
        for _ in 0..cnt {
            a.push(*num);
        }
    }
    // 可选：排序以匹配示例顺序
    a.sort();
}

// 测试代码
fn main() {
    let mut a = vec![1,2,3];
    let b = vec![2,2,3];
    merge_lists(&mut a, &b);
    println!("{:?}", a); // 输出 [1,2,2,3]
}

如果不需要保持元素顺序，这个实现的效率会更高；如果需要顺序，最后加个排序步骤就行。

针对问题2的优化建议 #

你的第一种实现用Vec存储质因数，每次通过filter计数的方式效率不高——毕竟每次filter都是O(n)的遍历操作。这里更适合用计数哈希表（比如HashMap<i64, usize>）来记录每个质因数需要保留的最大出现次数，优化后的实现如下：

use std::collections::HashMap;

fn prime_factors(mut n: i64) -> HashMap<i64, usize> {
    let mut factors = HashMap::new();
    let mut p = 2;
    while n >= p * p {
        if n % p == 0 {
            *factors.entry(p).or_insert(0) += 1;
            n /= p;
        } else {
            p += 1;
        }
    }
    *factors.entry(n).or_insert(0) += 1;
    factors
}

pub fn smallest_multiple(n: i64) -> i64 {
    let mut max_factors = HashMap::new();
    for p in 2..=n { // 从2开始即可，1没有质因数
        let pfs = prime_factors(p);
        for (prime, &count) in pfs.iter() {
            // 保留当前质因数的最大出现次数
            *max_factors.entry(*prime).or_insert(0) = count.max(*max_factors.get(prime).unwrap_or(&0));
        }
    }
    // 计算所有质数最大次幂的乘积
    max_factors.iter().fold(1, |acc, (&prime, &count)| acc * prime.pow(count as u32))
}

这种方式避免了反复遍历Vec计数的开销，效率会提升不少。另外，你用gcd+lcm的第二种实现其实已经非常简洁高效了，因为LCM的性质就是LCM(a,b,c) = LCM(LCM(a,b),c)，这种迭代计算的方式时间复杂度很低，也是解决该问题的最优思路之一。

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