剑指 Offer 39. 数组中出现次数超过一半的数字(python)
题目描述： 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 解题思路： 1.哈希 存储每个数字和其出现的次数，当次数大于长度的一半即返回，不用等到完全建立哈希表
class Solution:
def majorityElement(self, nums: List[int]) -> int:
n=len(nums)//2
dic={}
for i in nums:
dic[i]=1+dic.get(i,0)
if dic[i]>n:
return i
2.排序取中位数 由于是出现次数超过一半的数字，排序之后一定在数组的中间 3.摩尔投票法 每个数字和当前数字相同，次数+1，不同，数字-1，当次数为0时，更新当前数字，最后剩下的数字即为所求
cur,count=0,0
for i in nums:
if count==0:
cur,count=i,1
else:
if cur==i:
count+=1
else:
count-=1
#print(cur,i,count)
return cur
