haar_lib/algo/
majority_vote.rs1pub 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}