find majority element 28boyer e2 80 93moore majority vote algorithm 29

1def majorityElement(A):
2 
3    # `m` stores the majority element (if present)
4    m = -1
5 
6    # initialize counter `i` with 0
7    i = 0
8 
9    # do for each element `A[j]` in the list
10    for j in range(len(A)):
11 
12        # if counter `i` becomes 0
13        if i == 0:
14 
15            # set the current candidate to `A[j]`
16            m = A[j]
17 
18            # reset the counter to 1
19            i = 1
20 
21        # otherwise, increment the counter if `A[j]` is a current candidate
22        elif m == A[j]:
23            i = i + 1
24 
25        # otherwise, decrement the counter if `A[j]` is a current candidate
26        else:
27            i = i - 1
28 
29    return m