给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
codeType
输入：nums = [3,2,3]
输出：3
示例 2：
codeType
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
codeType
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
输入保证数组中一定有一个多数元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
解法：
python
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
'''
第一种想法就是遍历一遍数组，建立一个hash表把每种元素的出现次数记下来，出现次数大于n/2的就可以结束
时间复杂度是O(n) 但是这样空间复杂度就会是O(n)
第二种方法是可以用快排把元素按顺序排列，n/2位置的元素一定会是众数，也就是出现次数n/2的元素。
时间复杂度和空间复杂度就是排序的复杂度也就是nlogn
第三种方法就是随机找一个元素（主要是为了降低空间复杂度），判断该元素是否是众数，因为这个元素占比大于n/2所以选到的概率很大。
随机找到目标元素的次数的期望为2，也就是说大概率第2次就可以找到目标元素,这部分时间复杂度就是O(1)
而判断该元素是否是众数的时间复杂度是O(n)
所以总体的时间复杂度就是O(n),空间复杂度为O(1)
不过这种方法如果极端情况会发生永远也找不到目标元素的情况
我觉得可以按顺序进行目标查找，这样最差也会在n/2的位置找到目标元素
'''
maj_count = len(nums) // 2 # 向下取整
for i in range(0 , maj_count + 1): # 要注意只有一个元素的情况
# 该解法超时了，会卡在最坏的情况上
# if sum(1 for ele in nums if ele == nums[i]) > maj_count:
# return nums[i]
candidate = random.choice(nums)
if sum(1 for ele in nums if ele == candidate) > maj_count:
return candidate