[已解决]摩尔投票法对抗到底有啥用？

李二蛋

只要占比超过一半的元素称之为主要元素，那么只要挨个元素运行一遍统计阶段，肯定只有唯一的元素的数量超过总数的一半，
就完全能求出那个是主要元素了，为啥还要对抗呢？
很困惑，请求各位大神指点。

nums = [2, 2, 4, 2, 3, 6, 2]
   
# 对抗阶段
major = nums[0]
count = 0
for each in nums:
    if count == 0:
        major = each
    if each == major:
        count += 1
    else:
        count -= 1
   
# 统计阶段
if nums.count(major) > len(nums) / 2:
    print("主要元素是：", major)
else:
    print("不存在主要元素。")

最佳答案

月排行榜 / 总排行榜

大马强

2022-2-23 23:49:53

一个个的全数思路是对的，但你要考虑到时间，假设有10w个数，这样一个个数就会很慢，你最少要遍历10w次
摩尔投票法对抗运气好的话5w次解决

跳转到最佳答案楼层

大马强

一个个的全数思路是对的，但你要考虑到时间，假设有10w个数，这样一个个数就会很慢，你最少要遍历10w次
摩尔投票法对抗运气好的话5w次解决

李二蛋

大马强 发表于 2022-2-23 23:49
一个个的全数思路是对的，但你要考虑到时间，假设有10w个数，这样一个个数就会很慢，你最少要遍历10w次
摩 ...

明白了老铁，还需要考虑效率问题~感谢啦