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
