前言
小学编程练习中出现一道题，找出一组数（一定要有一个）中超过一半的数，按正常思路就是遍历一次hash统计，然后按值从大到小排序，这样排在第一的值应该是超过这组数数量的一半的，再取出这个键就是要找的数。
反正现在AI时代，也去AI问了一下，给出了一个算法：摩尔投票算法
介绍
摩尔投票法（Boyer–Moore majority vote algorithm），也被称作「多数投票法」，是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由罗伯特·S·博耶和J·斯特罗瑟·摩尔在1981年发表，也是处理数据流的一种典型算法。
其主要思想是通过不同元素之间的抵消来找到可能的主要元素候选者，并在最后验证候选者是否真正满足要求。算法的核心在于通过遍历数组，使用两个变量来记录当前候选的主要元素及其出现的次数。如果当前元素与候选元素相同，则增加计数器；如果不同，则减少计数器。最终剩下的元素即为出现次数超过一半的主要元素。
算法可以分为两个部分：
对抗：分属两个候选人的数量进行两两对抗抵消
计数：计算对抗结果中最后留下的候选人的数量是否有效
算法的具体实现步骤
- 初始化两个变量：
candidate用于保存候选主要元素，count用于记录候选主要元素出现的次数。初始时，candidate可以是任何数组中的元素，count初始化为0。 遍历数组中的每个元素：
如果count等于0，将当前元素设置为候选主要元素candidate，并将count设置为1。
如果count不等于0，检查当前元素是否等于candidate：如果相等，将
count递增1。
如果不相等，将count递减1。- 遍历完成后，
candidate变量中存储的元素就是数组中的主要元素。
代码
def find_majority_element(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count = 1
elif num == candidate:
count += 1
else:
count -= 1
return candidate
评论