Есть ли контейнер и метод для добавления списка B в список A, так что B является подмножеством A

Question

есть ли контейнер и / или метод в Rust для добавления списка элементов (B) в другой список элементов (A), так что B является подмножеством A? Кроме того, A и B могут содержать дубликаты.

Пример:

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

Я хотел бы получить:

A = {1, 2, 2, 3}

Обновление:

Я хочу решить 5-ю проблему проекта Эйлера (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 для решения smalllest_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
}

Answer 1

Вы можете использовать HashMap или BTreeMap, чтобы отслеживать каждое число (как ключ) и сколько раз оно повторяется (как значение). Затем вы можете обновить одну из этих карт на основе элементов в другой. Если вы хотите сохранить номера в порядке, BTreeMap сделает это автоматически:

use itertools::repeat_n;
use std::collections::BTreeMap;

fn count_repeats(inputs: &[u32]) -> BTreeMap<u32, usize> {
    inputs.iter().fold(BTreeMap::new(), |mut map, &n| {
        let count = map.entry(n).or_insert(0);
        *count += 1;
        map
    })
}

fn main() {
    let mut a = count_repeats(&[1, 2, 3]);
    let b = count_repeats(&[2, 2, 3]);

    for (n, count_b) in b {
        a.entry(n)
            .and_modify(|count_a| *count_a = count_b.max(*count_a))
            .or_insert(count_b);
    }

    let result: Vec<u32> = a
        .into_iter()
        .flat_map(|(&n, &count)| repeat_n(n, count))
        .collect();

    println!("{:?}", result); // [1, 2, 2, 3]
}

Answer 2

Если ваши последовательности отсортированы, вы можете использовать такую ​​функцию:

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]);
}