- 分类：分治/sort/位运算/vote/HashMap/Random
方法+时间/空间复杂度
169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
代码：
HashTable方法:
class Solution:
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return -1
count_table={}
len_=len(nums)
for i in range(len_):
if nums[i] not in count_table:
count_table[nums[i]]=1
else:
count_table[nums[i]]+=1
if count_table[nums[i]]>len_//2:
return nums[i]
return -1
随机数方法:
from random import randint
class Solution:
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return -1
len_=len(nums)
while (1):
my_num=nums[randint(0,len_-1)]
count=0
for n in nums:
if n==my_num:
count+=1
if count>len_//2:
return my_num
return -1
随机数方法:
from random import randint
class Solution:
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return -1
len_=len(nums)
while (1):
my_num=nums[randint(0,len_-1)]
count=0
for n in nums:
if n==my_num:
count+=1
if count>len_//2:
return my_num
return -1
Boyer-Moore Vote方法:
class Solution:
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return -1
len_=len(nums)
my_num=nums[0]
count=0
for n in nums:
if n==my_num:
count+=1
else:
count-=1
if count==0:
my_num=n
count=1
return my_num
位运算方法:
class Solution:
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return -1
len_=len(nums)
my_num=0
for i in range(32):
mask= 1 << i
count=0
for n in nums:
if (n & mask):
count+=1
if count>len_//2:
if i==31:
# if i==31,it means it is a negative number
my_num = -((1<<31)-my_num)
else:
my_num|=mask
return my_num
简单sort方法:
class Solution:
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return -1
return sorted(nums)[len(nums)//2]
分治方法:
class Solution:
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return -1
elif len(nums)==1:
return nums[0]
len_=len(nums)
left=self.majorityElement(nums[:len_//2])
right=self.majorityElement(nums[len_//2:])
if left==right:
return left
else:
count=0
for n in nums:
if n==left:
count+=1
if count>len_//2:
return left
else:
return right
讨论：
1.这道题咱们的速度图就不发了，毕竟这个题的算法特别多。
2.reference:花花酱
3.方法2BST和方法7部分排序法是C++自带方法，Python没有我就忽略，不实现了
