如何在Rust中删除数组中的重复项?

mspsb9vt  于 2022-11-24  发布在  其他
关注(0)|答案(3)|浏览(743)

我已经生成了一个数字数组。我想删除重复的数字。在javascript中,我可以只使用[...new Set(arr)]就可以完成这项工作。
在《铁 rust 》中,我还没有找到一个简单的方法来实现这一点。
我写过:

use rand::{thread_rng, Rng};
use itertools::Itertools;

fn main() {
    let mut arr:Vec<u8> = Vec::new();
    for _ in 0..10 {
        arr.push(thread_rng().gen_range(0..10))
    }
    println!("random {:?}", arr);
    arr.iter().unique();
    println!("unique {:?}", arr);
}

输出为:

random [7, 0, 3, 6, 7, 7, 1, 1, 8, 6]
unique [7, 0, 3, 6, 7, 7, 1, 1, 8, 6]

因此,我尝试在另一个变量中获得“无重复”结果:

let res = &arr.iter().unique();

结果是:

Unique { iter: UniqueBy { iter: Iter([1, 2, 0, 0, 7, 0, 2, 2, 1, 6]), used: {} } }

同样,在删除重复项之前,我似乎无法对数组进行排序。no method named 'iter' found for unit type '()' in the current scope method not found in '()' .

arr.sort().iter().unique();

另外,也许有一种方法可以在没有外部板条箱的情况下实现sort+unique value输出?

8yparm6h

8yparm6h1#

使用标准库

通常,对数组进行排序是一种不错的重复数据删除方法,但是,除非你使用基数排序(这不是Rust使用的排序方法),否则它比你在JS中所做的要好。

let a_vector = vec![7, 0, 3, 6, 7, 7, 1, 1, 8, 6];
let uniqued_vector = a_vector
    .into_iter()
    .collect::<HashSet<_>>()
    .into_iter()
    .collect::<Vec<_>>();

这会将数组转换为迭代器,然后将该迭代器转换为HashSet(这将对它进行重复数据删除),然后再次转换为迭代器形式,最后转换为数组。
看它on the playground
如果你想知道为什么我们必须在这些迭代器表示之间来回切换,那是因为它们是Rust用来将任何数据类型转换为其他数据类型的“接口”,非常高效,同时允许你在这一过程中轻松地执行一些操作。在这里,我们实际上不需要做任何事情,除了转换之外,这就是为什么它看起来有点冗长的原因。

使用itertools板条箱

itertools机箱提供了用于处理迭代器的实用程序(与我们用来在数据类型之间进行转换的接口相同)。然而,迭代器的一个特点是它们在某种程度上是懒惰的,从某种意义上说,它们本身并不是用来存储信息的数据类型。它们只表示通过可迭代接口在集合上执行的 * 操作 *。因此,您实际上需要将一个迭代器转换回一个可用的集合(或者以任何方式使用它),否则它将什么也不做(字面上)。
所以正确的代码版本可能是

let a_vector = vec![7, 0, 3, 6, 7, 7, 1, 1, 8, 6];
let uniqued_vector = a
    .into_iter()
    .unique()
    .collect::<Vec<_>>();

您不需要对任何内容进行排序,因为在内部,.unique()的工作方式与第一个实现非常相似。

对数组排序

如前所述,对数组进行排序是很好的,所以您可能仍然希望这样做。(Iterator特性没有提供这样的方法,a_vector.into_iter()生成的实际类型也没有提供这样的方法)!但是,一旦对数组进行了排序,您可能希望对其进行重复数据删除,也就是说,移除连续的重复,这也不是Iterator特性所能提供的。然而,这两个特性实际上都是Vec所能提供的,所以解决方案很简单:

let mut a_vector = vec![7, 0, 3, 6, 7, 7, 1, 1, 8, 6];
a_vector.sort();
a_vector.dedup();

然后a_vector包含唯一元素。
注意,只有在使用标准库的情况下才是这样。Itertools提供了sorted方法和dedup方法,因此使用itertools,您可以:

let a_vector = vec![7, 0, 3, 6, 7, 7, 1, 1, 8, 6];
let uniqued_vector = a_vector
    .into_iter()
    .sorted()
    .dedup()
    .collect::<Vec<_>>();

但此时最好使用.unique()
如果您想知道.iter().into_iter()之间的区别,请参阅this question

mitkmikd

mitkmikd2#

retain()例子的启发,我们可以依赖一个中间的布尔序列(参见下面的solution_1())。
我不太喜欢中间存储的想法,但我想(我应该进行基准测试,但我没有)这个简单的布尔向量比创建HashSet或排序要便宜。
对于一个 in-place 的解决方案,恐怕我们必须自己编写算法。这个技巧依赖于split_at_mut(),以避免 multiple-borrows 问题(参见下面的solution_2())。

use rand::{thread_rng, Rng};

fn solution_1(mut arr: Vec<u8>) -> Vec<u8> {
    println!("random {:?}", arr);
    let keep: Vec<_> = arr
        .iter()
        .enumerate()
        .map(|(i, x)| !arr[0..i].contains(x))
        .collect();
    let mut keep_iter = keep.iter();
    arr.retain(|_| *keep_iter.next().unwrap());
    println!("unique {:?}", arr);
    arr
}

fn solution_2(mut arr: Vec<u8>) -> Vec<u8> {
    println!("random {:?}", arr);
    let mut kept = 0;
    for i in 0..arr.len() {
        let (head, tail) = arr.split_at_mut(i);
        let x = tail.first_mut().unwrap();
        if !head[0..kept].contains(x) {
            if kept != i {
                std::mem::swap(&mut head[kept], x);
            }
            kept += 1;
        }
    }
    arr.resize(kept, Default::default());
    println!("unique {:?}", arr);
    arr
}

fn main() {
    let mut arr: Vec<u8> = Vec::new();
    for _ in 0..20 {
        arr.push(thread_rng().gen_range(0..10))
    }
    assert_eq!(solution_1(arr.clone()), solution_2(arr));
}
/*
random [2, 3, 6, 8, 4, 1, 1, 9, 1, 9, 1, 6, 2, 5, 5, 4, 0, 0, 5, 4]
unique [2, 3, 6, 8, 4, 1, 9, 5, 0]
random [2, 3, 6, 8, 4, 1, 1, 9, 1, 9, 1, 6, 2, 5, 5, 4, 0, 0, 5, 4]
unique [2, 3, 6, 8, 4, 1, 9, 5, 0]
*/
scyqe7ek

scyqe7ek3#

几件事:
1..unique()返回一个迭代器。您必须使用.collect(). This section of the Rust book contains the basic rules around using iterators将其转换回向量
1..sort()在适当的位置修改向量。单位类型表示表达式没有类型,函数有时可能没有任何输出,只是有副作用(如在适当的位置修改某些内容)。尝试:
arr.sort();
let uniques = arr.iter().unique().collect()

相关问题