题解 | #数组中出现次数超过一半的数字#
数组中出现次数超过一半的数字
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param numbers int整型一维数组
# @return int整型
#
"""
要解决这个问题，我们可以使用摩尔投票算法（Boyer-Moore Voting Algorithm）。
摩尔投票算法可以在线性时间复杂度O(n)和常数空间复杂度O(1)内找到出现次数超过一半的元素。
摩尔投票算法的基本思想是维护一个候选众数candidate和它的出现次数count。遍历数组，
如果count为0，我们假设当前遍历到的元素是候选众数，并将count设为1。
如果count不为0，我们检查当前元素是否等于candidate，如果等于，count加1，否则count减1。
遍历完数组后，candidate就是我们要找的众数。
"""
class Solution:
def MoreThanHalfNum_Solution(self, numbers: List[int]) -> int:
candidate = None
count = 0
for num in numbers:
if count == 0:
candidate = num
if num == candidate:
count += 1
else:
count -= 1
return candidate
查看30道真题和解析
投递拓竹科技等公司10个岗位