LeetCode-169-多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于n/2的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

image.png

解题思路：

1. 字典存储出现次数；
2. 排序后求众数；
3. 遍历一次，不等就消除，相等则累计。

Python3代码：

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans = {}
        n = len(nums)
        if n==1:
            return nums[0]
        for i in range(n):
            if nums[i] not in ans:
                ans[nums[i]]=1
            else:
                ans[nums[i]]+=1
                if ans[nums[i]]>n//2:
                    return nums[i]

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

class Solution: 
    def majorityElement(self, nums: List[int]) -> int:
        ans = nums[0]
        len1 = 1
        for i in range(1, len(nums)):
            if nums[i] == ans: # 相等说明重复两个数字
               len1+=1
            else: # 不等
                if len1 > 0:  # 消除
                    len1-=1 
                else:
                    ans=nums[i]
                    len1 = 1
        return ans