1pub trait MajorityVote {
2 type Item;
3 fn majority_vote(&self) -> Option<(&Self::Item, usize)>;
4}
5
6impl<T: Eq> MajorityVote for [T] {
7 type Item = T;
8 fn majority_vote(&self) -> Option<(&T, usize)> {
9 let mut maj = self.get(0)?;
10 let mut vote = 1;
11 let n = self.len();
12 for x in &self[1..] {
13 if maj == x {
14 vote += 1;
15 } else if vote == 0 {
16 maj = x;
17 vote = 1;
18 } else {
19 vote -= 1;
20 }
21 }
22
23 let mut vote = 0;
24 let mut occ = 0;
25 for (i, x) in self.iter().enumerate().rev() {
26 if maj == x {
27 vote += 1;
28 occ = i;
29 }
30 }
31 (vote > n - vote).then(|| (&self[occ], vote))
32 }
33}
34
35#[test]
36fn sanity_check() {
37 assert_eq!([1].majority_vote(), Some((&1, 1)));
38 assert_eq!([1, 2, 1, 2, 1].majority_vote(), Some((&1, 3)));
39 assert_eq!([1, 2, 1, 2, 3].majority_vote(), None);
40 assert_eq!([1, 2, 1, 2].majority_vote(), None);
41
42 let empty: [i32; 0] = [];
43 assert_eq!(empty.majority_vote(), None);
44}