时间戳

首页 > 解决方案 > 是否有将列表 B 添加到列表 A 的容器和方法，以便 B 是 A 的子集

rust - 是否有将列表 B 添加到列表 A 的容器和方法，以便 B 是 A 的子集

问题描述

Rust 中是否有容器和/或方法可以将元素列表 (B) 添加到另一个元素列表 (A) 中，以使 B 成为 A 的子集？此外，A 和 B 都可以包含重复项。

例子：

A = {1, 2, 3}
B = {2, 2, 3}

我想得到：

A = {1, 2, 2, 3}

更新：

我想解决项目欧拉的第五个问题（https://projecteuler.net/problem=5）。我目前的解决方案如下：

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()
}

Rust 中是否有任何集合类型或其他东西来解决 minimum_multiple()？

我知道这个问题可以使用 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
}

标签： rustcontainers

解决方案

如果您的序列已排序，您可以使用如下函数：

fn combine(first: &[u32], second:&[u32])->Vec<u32>{
    if first.is_empty(){
        return second.to_vec();
    }
    if second.is_empty(){
        return first.to_vec();
    }
    // I will assume that both sorted
    let mut first_counted: Vec<(u32, usize)> = Vec::with_capacity(first.len());
    for &item in first.iter(){
        match first_counted.last_mut(){
            Some(last) if last.0 == item =>{
                last.1 += 1;
            },
            _ => first_counted.push((item, 1)),
        };
    }

    let mut second_counted: Vec<(u32, usize)> = Vec::with_capacity(second.len());
    for &item in second.iter(){
        match second_counted.last_mut(){
            Some(last) if last.0 == item => {
                last.1 += 1;
            },
            _ => second_counted.push((item, 1)),
        };
    }
    let mut res = Vec::with_capacity(std::cmp::max(first.len(),second.len()));
    let mut fidx = 0;
    let mut sidx = 0;
    while fidx < first_counted.len() && sidx < second_counted.len(){
        let f = &first_counted[fidx];
        let s = &second_counted[sidx];
        match f.0.cmp(&s.0){
            std::cmp::Ordering::Less=>{
                res.resize(res.len()+f.1, f.0);
                fidx+=1;
            },
            std::cmp::Ordering::Equal=>{
                res.resize(res.len()+std::cmp::max(f.1, s.1), f.0);
                fidx+=1;
                sidx+=1;
            },
            std::cmp::Ordering::Greater=>{
                res.resize(res.len()+s.1, s.0);
                sidx+=1;
            },
        }
    }
    res
}

fn main() {
    assert_eq!(combine(&[1, 2, 3], &[2, 2, 3]), vec![1,2,2,3]);
}

推荐阅读