0169 多数元素.md

Lamarck      

0169 多数元素

---

01 哈希表 o(n) (空间复杂度是o(n))

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        target = (len(nums)-1) // 2
        myDict = {}
        for num in nums:
            if num not in myDict:
                myDict[num] = 1
            else:
                myDict[num] += 1
        for key in myDict:
            if myDict[key] > target:
                return key

02 Boyer–Moore多数投票算法 o(n) (空间复杂度是o(1))

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = None
        cnt = 0
        for num in nums:
            if cnt == 0:
                ans = num
            if ans == num:
                cnt += 1
            else:
                cnt -= 1
        return ans