# Leetcode 229. Majority Element II

## 題解

### 二分搜索

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # Time compelxity: O(nlogn)
        # Space complexity: O(n) 
        nums.sort()
        n = len(nums)
        n3 = n // 3 
        def binary_search_bound(target: int, bound: bool, start_at: int):
            left = start_at
            right = n - 1 
            ans = -1

            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    ans = mid
                    if bound:
                        left = mid + 1
                    else:
                        right = mid - 1
                else:
                    if nums[mid] > target:
                        right = mid - 1
                    else:
                        left = mid + 1
            return ans
        
        output = []
        left = 0
        while left < n:
            right = binary_search_bound(nums[left],True,left)
            c = right - left + 1
            if c > n3:
                output.append(nums[left])
            left = right + 1
        
        return output

### 哈希表

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # Time complexity: O(n)
        # Space complexity: O(1)
        n = len(nums)
        counts = {}
        output = []
        for num in nums:
            if num in counts:
                counts[num] += 1
            else:
                counts[num] = 1
        for key in counts:
            value = counts[key]
            if value > n // 3:
                output.append(key)
        return output

### 摩爾投票法

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # Time complexity: O(n)
        # Space complexity: O(1)
        element1 = element2 = vote1 = vote2 = 0
        for num in nums:
            if vote1 > 0 and num == element1:
                vote1 += 1
            elif vote2 > 0 and num == element2:
                vote2 += 1
            elif vote1 == 0:
                element1 = num
                vote1 += 1
            elif vote2 == 0:
                element2 = num
                vote2 += 1
            else:
                vote1 -= 1
                vote2 -= 1
        n = len(nums)
        ans = []
        cnt1 = cnt2 = 0
        for num in nums:
            if vote1 > 0 and num == element1:
                cnt1 += 1
            if vote2 > 0 and num == element2:
                cnt2 += 1
        if vote1 > 0 and cnt1 > n // 3:
            ans.append(element1)
        if vote2 > 0 and cnt2 > n // 3:
            ans.append(element2)
        return ans