TheAlgorithms-Python

1
"""
2
This is Booyer-Moore Majority Vote Algorithm. The problem statement goes like this:
3
Given an integer array of size n, find all elements that appear more than ⌊ n/k ⌋ times.
4
We have to solve in O(n) time and O(1) Space.
5
URL : https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm
6
"""
7

8
from collections import Counter
9

10

11
def majority_vote(votes: list[int], votes_needed_to_win: int) -> list[int]:
12
    """
13
    >>> majority_vote([1, 2, 2, 3, 1, 3, 2], 3)
14
    [2]
15
    >>> majority_vote([1, 2, 2, 3, 1, 3, 2], 2)
16
    []
17
    >>> majority_vote([1, 2, 2, 3, 1, 3, 2], 4)
18
    [1, 2, 3]
19
    """
20
    majority_candidate_counter: Counter[int] = Counter()
21
    for vote in votes:
22
        majority_candidate_counter[vote] += 1
23
        if len(majority_candidate_counter) == votes_needed_to_win:
24
            majority_candidate_counter -= Counter(set(majority_candidate_counter))
25
    majority_candidate_counter = Counter(
26
        vote for vote in votes if vote in majority_candidate_counter
27
    )
28
    return [
29
        vote
30
        for vote in majority_candidate_counter
31
        if majority_candidate_counter[vote] > len(votes) / votes_needed_to_win
32
    ]
33

34

35
if __name__ == "__main__":
36
    import doctest
37

38
    doctest.testmod()
39