[LeetCode] 169. Majority Element

Problem : https://leetcode.com/problems/majority-element/

Since majority element appears more than n/2 times, number[n/2] in the sorted array must be the majority element.

Time Complexity = O ( N * Log N )

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

Use counter to filter out minority element.

Time Complexity = O ( N )

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        result = nums[0]
        count = 1
        
        for i in range(1, len(nums)):
            if nums[i] == result:
                count += 1
            else:
                count -= 1
            
            if count == 0:
                result = nums[i]
                count = 1
        
        return result