rust 算法题求优化之 数组交集并排字典序

英文原文描述:

Description:
Given two arrays of strings a1 and a2 return a sorted array r in lexicographical order of the strings of a1 which are substrings of strings of a2.

#Example 1: a1 = [“arp”, “live”, “strong”]

a2 = [“lively”, “alive”, “harp”, “sharp”, “armstrong”]

returns [“arp”, “live”, “strong”]

#Example 2: a1 = [“tarp”, “mice”, “bull”]

a2 = [“lively”, “alive”, “harp”, “sharp”, “armstrong”]

returns []

Notes:
Arrays are written in “general” notation. See “Your Test Cases” for examples in your language.

In Shell bash a1 and a2 are strings. The return is a string where words are separated by commas.

Beware: r must be without duplicates.
Don’t mutate the inputs.

中文简述:

也就是 a1 可能是 a2 的子集,返回的必须是 a1 与 a2 交集的字典排序后的数组。

题目函数头:

fn in_array(arr_a: &[&str], arr_b: &[&str]) -> Vec<String> {
    todo!();
}

我的题解:

fn in_array(arr_a: &[&str], arr_b: &[&str]) -> Vec<String> {
    let mut vec:Vec<String> = Vec::new();
    for &i in arr_a {
        for &j in arr_b {
            if j.contains(i) && !vec.contains(&String::from(i)) {
                vec.push(String::from(i));
            }
        }
    }
    vec.sort();
    vec
}

有没有更优的解呢?

最佳答案

下面是根据你所提供的题意做的:

fn in_array(arr_a: &[&str], arr_b: &[&str]) -> Vec<String> {
    let mut vec: Vec<String> = arr_a.iter().filter(|&&str1| arr_b.iter().any(|&str2| str2.contains(&str1))).map(|&s| String::from(s)).collect();
    vec.sort();
    vec.dedup();
    vec
}
3年前 评论
lve_me (楼主) 3年前
讨论数量: 2

下面是根据你所提供的题意做的:

fn in_array(arr_a: &[&str], arr_b: &[&str]) -> Vec<String> {
    let mut vec: Vec<String> = arr_a.iter().filter(|&&str1| arr_b.iter().any(|&str2| str2.contains(&str1))).map(|&s| String::from(s)).collect();
    vec.sort();
    vec.dedup();
    vec
}
3年前 评论
lve_me (楼主) 3年前

你的至少O(n ^ 3),我的低一个数量级

3年前 评论
lve_me (楼主) 3年前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!