如何檢查切片中是否有重複？

是否有一種本地方法來檢查切片是否有重複？現在我用這個：如何檢查切片中是否有重複？

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會照顧這樣簡單的循環。儘管如此，你在一般情況下是正確的。 –

如何檢查切片中是否有重複？

回答

相關問題