169.多数元素

解题思路

解法一：排序法

如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 ⌊n/2⌋ 的元素（下标从 0 开始）一定是众数。
复杂度分析：
时间复杂度：O(nlogn)。将数组排序的时间复杂度为 O(nlogn)。
空间复杂度：O(logn)。如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间。如果自己编写堆排序，则只需要使用 O(1)的额外空间。

解法二：Boyer-Moore 投票法

我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0。然后遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
在遍历完成后，candidate 即为整个数组的众数。

复杂度分析：
时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
空间复杂度：O(1)。Boyer-Moore 算法只需要常数级别的额外空间。

解法三：哈希字典法

遍历数组，如果在字典中，则对应的值加1，否则将其加入字典。最后遍历一遍字典，返回值大于n/2的键。

代码

解法一：排序法

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:
        count = 0
        candidate = None
        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if candidate == num else -1)
        return candidate

解法三：哈希字典法

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