Majority Element with Boyer–Moore majority vote algorithm

This algorithm finds a majority element, if there is one: that is, an element that occurs repeatedly for more than half of the elements of the input in linear time O(n) and a constant space O(1) .

def majority_element(nums):
    answer = None
    count = 0

    for num in nums:
        if count == 0:
            answer = num
        count += (1 if num == answer else -1)

    return answer # assumes a majority element always exists

def pr(ok): print("Ok" if ok else "Error")

pr(2 == majority_element([2, 2, 1, 1, 1, 2, 2]))
pr(3 == majority_element([3,2,3]))

A majority element is not equal to the most frequent element.

majority_element([3, 2, 3, 2, 1, 3]) # Return: 1

If you don’t know whether there is a majority element and you want to return the majority element if there exists; Otherwise return None. Make a second pass through the data to verify that the element is a majority.

    count = 0
    for num in nums:
        if num == answer:
            count += 1

    if count <= len(nums) // 2:
        answer = None

References: