haar_lib/algo/
majority_vote.rs

1//! Boyer-Moore majority vote algorithm
2
3/// Boyer-Moore majority vote algorithm
4///
5/// **Time complexity** $O(n)$
6pub fn majority_vote<T: Eq>(a: &[T]) -> Option<(&T, usize)> {
7    let mut candidate = None;
8    let mut counter = 0;
9
10    for x in a {
11        if counter == 0 {
12            candidate = Some(x);
13            counter = 1;
14        } else {
15            match candidate {
16                Some(y) if x == y => counter += 1,
17                _ => counter -= 1,
18            }
19        }
20    }
21
22    if let Some(x) = candidate {
23        let count = a.iter().filter(|&y| x == y).count();
24        if count <= a.len() / 2 {
25            None
26        } else {
27            Some((x, count))
28        }
29    } else {
30        None
31    }
32}
33
34#[cfg(test)]
35mod test {
36    use super::*;
37    use rand::Rng;
38    use std::collections::BTreeMap;
39
40    fn check<T: Eq + Ord>(a: &[T]) -> Option<(&T, usize)> {
41        let mut map = BTreeMap::<&T, usize>::new();
42        let h = a.len() / 2;
43
44        for x in a {
45            *map.entry(x).or_insert(0) += 1;
46        }
47
48        for (k, v) in map {
49            if v > h {
50                return Some((k, v));
51            }
52        }
53        None
54    }
55
56    #[test]
57    fn test() {
58        let mut rng = rand::thread_rng();
59
60        for _ in 0..100 {
61            let n = rng.gen_range(0..=100);
62            let a = (0..n).map(|_| rng.gen::<u64>() % 10).collect::<Vec<_>>();
63
64            assert_eq!(check(&a), majority_vote(&a));
65        }
66    }
67}