如何检查切片中是否有重复？

是否有一种本地方法来检查切片是否有重复？现在我用这个：如何检查切片中是否有重复？

fn has_dup<T: PartialEq>(slice: &[T]) -> bool { 
    for i in 1..slice.len() { 
     if slice[i..].contains(&slice[i - 1]) { 
      return true; 
     } 
    } 
    false 
} 

fn main() { 
    use std::ops::Not; 

    assert!(has_dup(&[1, 2, 3, 2, 5, 6])); 
    assert!(has_dup(&[1, 2, 3, 4, 5, 6]).not()); 
}

但是对于这种基本操作，我不喜欢用手工编码。

如果在标准库中没有可用的函数来执行此操作，是否可以优化我的代码？我知道索引切片不是最优化的方式（for i in slice {} vs for i in 0..slice.len() { slice[i] }）。

来源

2017-10-16 Boiethios

这基本上是[Element distinctness problem]（https://en.wikipedia.org/wiki/Element_distinctness_problem）。比检查每个元素与列表的其余部分是'O（n^2）'还是更有效的方法，但是这些都没有在std中实现。然而，这种折衷是他们可能需要更多的记忆。在rosetta-code上查看[使用HashSet移除dupes]的方法（https://github.com/Hoverbear/rust-rosetta/blob/master/tasks/remove-duplicate-elements/src/main.rs）。这是删除vs只是检查，但它应该让你知道如何做到这一点。 –

@PaoloFalabella这很奇怪，这样一个基本的算法不在std中。 – Boiethios

@Boiethios为什么你认为这是一个“基本”算法？即使是这样，请记住许多人认为“基本”的*随机数生成*是由一个箱子提供的。 – Shepmaster

在算法复杂度而言，它往往是更好地跟踪唯一值的索引。如果你能Hash和Eq检查平等，你可以试试这个效用函数：

fn has_unique_elements<T>(iter: T) -> bool 
where 
    T: IntoIterator, 
    T::Item: Eq + Hash, 
{ 
    let mut uniq = HashSet::new(); 
    iter.into_iter().all(move |x| uniq.insert(x)) 
} 

assert!(!has_unique_elements(vec![10, 20, 30, 10, 50])); 
assert!(has_unique_elements(vec![10, 20, 30, 40, 50])); 
assert!(has_unique_elements(Vec::<u8>::new()));

Playground

同样的，如果你的元素没有实现Hash但确实实现Ord，你可以使用一个BTreeSet代替（Playground）。

来源

2017-10-16 10:05:44

我喜欢这个解决方案，但是对类型有更多限制（'Hash' +'Clone'） – Boiethios

无法打破煎蛋而没有打破鸡蛋。：P哈希函数或总顺序关系对于快速查找都是必需的。我不确定是否可以避免复制以前提取的项目。 –

是否可以使用'.cloned（）。all（move | x | uniq.insert（x））'?.应该不需要'ExactSizeIterator'约束。 – Boiethios

索引是不是最少优化，它只是不存在迭代器解决方案存在的地方。没有迭代器解决方案，因此您的代码已经是最佳解决方案。

如果你想下去更具功能性的道路，你可以写

(1..slice.len()).any(|i| slice[i..].contains(&slice[i - 1]))

来源

2017-10-16 09:15:54

索引检查检查索引是否在边界内。所以有一个（小的）开销。但是这个小开销可以在循环中产生更大的差异。 – Boiethios

LLVM会照顾这样简单的循环。尽管如此，你在一般情况下是正确的。 –

如何检查切片中是否有重复？

回答

相关问题