题目要求:
关键在于时间复杂度在O(N),每次只对数组做一次遍历
题解:
1.MAP
对数组进行一次遍历,记录数组中每个元素出现的次数并保存在map中,对map进行一次搜索,找到出现次数大于数组长度一半的主要元素
<1>map times初始为空,对数组nums进行遍历,若当前元素在times中不存在,则加入,若已经存在则其对应次数加一
<2>数组遍历结束后,遍历times,找到出现次数大于二分之一数组大小的元素,如果没有则返回-1
def majorityElement(self,nums):
times = {}
mylen = len(nums)
for i in range(mylen):
if nums[i] in times:
times[nums[i]]+=1
else:
times[nums[i]]=1
for i in range(mylen):
number = times[nums[i]]
if number>mylen//2:
return nums[i]
return -1
2.摩尔投票算法
每次从数组中去掉两个不同的元素,最后剩余的元素就是主要元素或者是最后剩余的元素,结束后遍历一次数组,判断是否为主要元素。
<1>number用来记录数值,times记录出现次数。
<2>从数组第一位开始遍历,times=0说明遍历刚开始或者已经删除了一对不相等的元素,将数组当前元素赋给number
<3>若times不为0,判断nums[i]是否和number相等,不等则times-1,相当于删除nums[i]与一个number,相等则times+1,number出现次数加一。
<4>遍历一次后将得到一个number,再次遍历数组记录number出现次数,判断是否为主要元素。
def majorityElement(self,nums):
number = 0
times = 0
for i in range(len(nums)):
if times==0:
number = nums[i]
times = 1
else:
if number==nums[i]:
times+=1
else:
times=times-1
count = 0
for i in range(len(nums)):
if nums[i]==number:
count=count+1
if count>len(nums)/2:
return number
return -1