哇看到第一眼就是用哈希表，随手写了一下，没想到有更快的另外两种方法，先写一部分吧，今天不想写了哈哈哈。那第一个方法就不用说了吧。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
第二个思路也很简单，就是先把数组拍序，中位数必定是所求的数。因为出现次数多于一半的话，连续相同的这个数必定跨度大于数组的一半。这个算法的时间复杂度为O（NlogN）。
第三个思路是用快速排序来做，这个等弄完排序专题再来补充。
还有另外一个方法，叫做摩尔投票法，这个算法首先用一个votes来记录票数和，并且规定记众数的票数为+1，非众数的票数为-1，那么由于众数的数量大于总数的一半，故对于整个数组来说，最后的votes值肯定大于0。还有一个特性，当从前往后遍历数组时，若前a个数的votes值为0，则数组后（n-a）个数字的票数和一定大于0（即后n-a个数字中的众数也一定是原先的众数）。算法流程如代码所示，首先设票数和votes为0，x为众数，从头开始遍历数组，当votes为0时，设置遍历到的num为众数x，当num与x相等时，votes加一，否则votes减一，最后将x返回即可。这个的时间复杂度是O（N），空间复杂度是O（1）。
class Solution:
def majorityElement1(self, nums: List[int]) -> int:
if not nums:
return None
if len(nums) == 1:
return nums[0]
dic = {}
for num in nums:
if num not in dic.keys():
dic[num] = 1
else:
dic[num] += 1
if dic[num] > len(nums) // 2:
return num
def majorityElement2(self, nums: List[int]) -> int:
return sorted(nums)[len(nums)//2]
def majorityElement3(self, nums: List[int]) -> int:
votes = 0
for num in nums:
if votes == 0:
x = num
if x != num:
votes -= 1
else:
votes += 1
return xPREVIOUSjz037.序列化二叉树