#Method 1
import math
class Solution(object):
    def majorityElement(self, nums):
        numsDic={}
        for num in nums:
            numsDic[num]=numsDic[nums]+1 if num in numsDic else 0
            if numsDic[num]>len(nums)/2:
                return num

#Method 2
#这种方法的思想是把 majority element 看成是 1，而把其他的元素看成是 -1。
#算法首先取第一个元素 x 作为 majority element，并计 mark = 1；
#而后遍历所有的元素，如果元素和 x 相等， 则 mark ++；
#否则如果不等， 则 mark--, 如果 mark == 0, 则重置 mark = 1， 并且更新 x 为当前元素。
#由于majority element 的数量大于一半，所以最后剩下的必然是majority element.

class Solution(object):
    def majorityElement(self, nums):
        mark=1
        x=nums[0]
        for i in range(1,len(nums)):
           
            if(mark==0):
                mark=1;x=nums[i]
            elif(nums[i]==x):
                mark+=1
            elif(nums[i]!=x):
                mark-=1
       
        return x