169. Majority Element

hash table 
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        hash_table={}
        for num in nums:
            if num in hash_table:
                hash_table[num]+=1
            else:
                hash_table[num]=1
        return max(hash_table,key=lambda x:hash_table[x])

moore's voting algrithm 
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        candidate=nums[0]
        count=1
        for num in nums[1:]:
            if count==0:
                candidate=num
                count=1
            elif num ==candidate:
                count+=1
            else: 
                count-=1
        return candidate

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #bit manipulation
        bit=[0]*32
        res=0
        for num in nums:
            for i in range(32):
                bit[i]+=(num>>i)&1
        for i, val in enumerate(bit):
            if val>len(nums)/2:
                
                
                res|=(1<<i) 
                if i==31:#negative number, 2's complement =val-2^N
                    res-=(1<<32)
        return res