Majority Element

Problem: Majority Element

We can use voting algorithm to solve this problem. A majority element must occur twice in consecutive 3 numbers.

Code in Python:

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        x, c = None, 0
        for num in nums:
            if c == 0: x, c = num, 1
            elif num == x: c += 1
            else: c -= 1
        return x
        # count = 0
        # for num in nums:
        #     if num == x: count += 1
        # return x if count > len(nums)/2 else None

Notice that the commented part actually checks whether our answer is a majority element, which I think is quite essential, but not covered in test cases.