169. Majority Element

Solution 1: Counter

from collections import Counter
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majElmt = Counter(nums).most_common(1)
        return majElmt[0][0]

Time Complexity: O(N)
Space Complexity: O(N)

Solution 2: Sorting

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        return nums[n // 2]

Time Complexity: O(NLog(N))
Space Complexity: O(1)

Solution 3: Recursive

Time Complexity: O(NLog(N))
Space Complexity: O(Log(N))

Solution 4: Boyer–Moore majority vote algorithm

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count, majorElmt = 0, nums[0]
        for elmt in nums:
            if count == 0:
                majorElmt = elmt
                count = 1
            elif count > 0 and majorElmt != elmt:
                count -= 1
            elif count > 0 and majorElmt == elmt:
                count += 1
        return majorElmt

Time Complexity: O(N)
Space Complexity: O(1)

Solution 5: Bit Manipulation

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majorElmt = 0
        for bitI in range(32):
            bitICount = 0
            for val in nums:
                bitMask = 1 << bitI
                if val & bitMask:
                    bitICount += 1
            if bitICount > len(nums) // 2:
                majorElmt |= bitMask
        return majorElmt

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/majority-element/discuss/51612/C%2B%2B-6-Solutions