剑指Offer 39. 数组中出现次数超过一半的数字（Easy）
【题目链接】
题解
投票法python题解–sort()、快排、字典、抵消等四种方法
思路
方法一：哈希表（字典）
class Solution(object):
def majorityElement(self
, nums
):
if len(nums
) == 1:
return nums
[0]
d
= {}
for num
in nums
:
if num
in d
:
d
[num
] += 1
if d
[num
] > len(nums
) // 2:
return num
else:
d
[num
] = 1
方法二：投票法
class Solution(object):
def majorityElement(self
, nums
):
"""
:type nums: List[int]
:rtype: int
"""
vote
= 0
for num
in nums
:
if vote
== 0:
mode
= num
if mode
== num
:
vote
+= 1
else:
vote
-= 1
count
= 0
for num
in nums
:
if num
== mode
:
count
+= 1
return mode
if count
> len(nums
) // 2 else -1
