解题思路
解法一：排序法
如果将数组 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
