0229. Majority Element II - chasel2361/leetcode GitHub Wiki

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Note: The algorithm should run in linear time and in O(1) space.

Example 1:
Input: [3,2,3]
Output: [3]

Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

這題是上一題的延伸，題目的限制從長度的二分之一改為三分之一，所以同樣能夠使用摩爾投票法來解決，差別只在於一次刪除三個數，以及最後要重新計算取出的兩個數是否大於長度三分之一

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if not nums: return []
        n1 = nums[0]
        n2 = None
        cnt_1 = 1
        cnt_2 = 0
            
        for i in range(1, len(nums)):
            if nums[i] == n1:
                cnt_1 += 1
            elif n2 == None:
                n2 = nums[i]
                cnt_2 = 1
            elif nums[i] == n2:
                cnt_2 += 1
            elif cnt_1 == 0:
                n1 = nums[i]
                cnt_1 = 1
            elif cnt_2 == 0:
                n2 = nums[i]
                cnt_2 = 1
            else:
                cnt_1 -= 1
                cnt_2 -= 1
            
        cnt_1, cnt_2 = 0, 0
        for n in nums:
            if n == n1:
                cnt_1 += 1
            if n == n2:
                cnt_2 += 1
        
        res = []
        if cnt_1 > len(nums) // 3:
            res.append(n1)
        if cnt_2 > len(nums) // 3:
            res.append(n2)

這樣寫的時間複雜度是 O(N)，空間複雜度是 O(1)

---

不過這樣比起來，感覺 hashmap 的寫法似乎比較方便且簡潔，只要把 nums 全部丟進 collections.Counter，再確認每個 key 對應的 value 是否大於三分之長度就可以了

from collections import Counter
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        numMap = Counter(nums)
        res = []
        for k, v in numMap.items():
            if v > len(nums) // 3:
                res.append(k)
        return res

這個方法跟摩爾投票法比較起來比較明顯的缺點是空間複雜度較高 (O(N))

但時間複雜度相同，亦為 O(N)