nekolib/algo/majority_.rs
1//! Boyer--Moore's majority vote algorithm。
2
3/// Boyer--Moore's majority vote algorithm。
4///
5/// 過半数の出現数を持つ要素があれば、それを返す。
6///
7/// # Idea
8/// `todo!()`
9///
10/// # Complexity
11/// $O(n)$ time.
12///
13/// # Examples
14/// ```
15/// use nekolib::algo::majority;
16///
17/// assert_eq!(majority(&[1, 1, 3, 2, 1]), Some(&1));
18/// assert_eq!(majority(&[9]), Some(&9));
19/// assert_eq!(majority(&[6, 7]), None);
20/// assert_eq!(majority::<i32>(&[]), None);
21/// ```
22pub fn majority<T: Eq>(buf: &[T]) -> Option<&T> {
23 if buf.is_empty() {
24 return None;
25 }
26 let mut maj = &buf[0];
27 let mut vote = 1;
28 let n = buf.len();
29 for x in buf.iter().skip(1) {
30 if maj == x {
31 vote += 1;
32 } else if vote == 0 {
33 maj = x;
34 vote = 1;
35 } else {
36 vote -= 1;
37 }
38 }
39 let mut vote = 0;
40 let mut first = 0;
41 for (i, x) in buf.iter().enumerate().rev() {
42 if maj == x {
43 vote += 1;
44 first = i;
45 }
46 }
47 if vote > n - vote {
48 Some(&buf[first])
49 } else {
50 None
51 }
52}