rust_dsa/
mjrty.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/// Returns the majority element of an iterator, if one exists.
///
/// This is an implementation of the MJRTY algorithm described by Boyer and Moore in
/// ["MJRTY - A Fast Majority Vote Algorithm."](https://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html)
///
/// # Example
/// ```
/// use rust_dsa::majority_element;
///
/// let ints = vec![1, 2, 1, 3, 1, 4, 3, 2, 1, 1, 1];
/// let winner = majority_element(ints.into_iter());
/// assert_eq!(winner, Some(1));
///
/// let strs = vec!["a", "c", "b", "a"];
/// let winner = majority_element(strs.into_iter());
/// assert_eq!(winner, None);
/// ```
pub fn majority_element<I>(elements: I) -> Option<I::Item>
where
    I: Iterator + Clone,
    I::Item: Eq,
{
    let mut confidence = 0;
    let mut option_winner = None;

    for elem in elements.clone() {
        // update `option_winner` using the MJRTY update rules
        option_winner = if let Some(winner) = option_winner {
            if winner == elem {
                // found a match, increment `confidence`
                confidence += 1;
                Some(winner)
            } else if confidence > 1 {
                // not a match, but `confidence` is still positive
                confidence -= 1;
                Some(winner)
            } else {
                // not a match, `confidence` is `0`
                confidence = 0;
                None
            }
        } else {
            // we don't have a guess, so set `option_winner` to the current element
            confidence = 1;
            Some(elem)
        }
    }

    if let Some(winner) = option_winner {
        // do one more pass to make sure we don't have a false positive
        let mut matches = 0;
        let mut total = 0;
        for elem in elements {
            if elem == winner {
                matches += 1;
            }
            total += 1;
        }

        if matches > total / 2 {
            return Some(winner);
        }
    }
    None
}