[已解决]摩尔投票

spflmm

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("不存在主要元素。")

请问：
if count == 0:
major = each

这是什么意思？
真正的零基础，请大神赐教，谢谢！

最佳答案

月排行榜 / 总排行榜

isdkz

2023-3-16 13:40:16

这段代码是用来找一个列表（nums）中出现次数超过一半的元素（主要元素）。如果存在这样的元素，就输出这个元素，否则输出"不存在主要元素。"

这个算法分为两个阶段：对抗阶段（Boyer-Moore 投票算法）和统计阶段。

对抗阶段的主要思路是：遍历整个列表，维护一个候选主要元素（major）和一个计数器（count）。如果计数器为0，我们将当前遍历到的元素赋值给候选主要元素。然后，如果当前元素等于候选主要元素，计数器加1；如果不等于，计数器减1。

这里的：

if count == 0:
    major = each

意味着，如果当前计数器为0，我们将当前遍历到的元素（each）赋值给候选主要元素（major）。这是因为当计数器为0时，表示之前遍历过的元素中没有一个元素的数量超过一半，所以我们需要用当前元素作为新的候选主要元素。

对抗阶段完成后，我们会得到一个候选主要元素。然后，在统计阶段，我们计算这个候选主要元素在列表中出现的次数。如果它的出现次数大于列表长度的一半，那么它就是主要元素，否则不存在主要元素。

这个算法的优点是时间复杂度为O(n)，空间复杂度为O(1)，在处理大数据时非常高效。

跳转到最佳答案楼层

isdkz

这段代码是用来找一个列表（nums）中出现次数超过一半的元素（主要元素）。如果存在这样的元素，就输出这个元素，否则输出"不存在主要元素。"

这个算法分为两个阶段：对抗阶段（Boyer-Moore 投票算法）和统计阶段。

对抗阶段的主要思路是：遍历整个列表，维护一个候选主要元素（major）和一个计数器（count）。如果计数器为0，我们将当前遍历到的元素赋值给候选主要元素。然后，如果当前元素等于候选主要元素，计数器加1；如果不等于，计数器减1。

这里的：

if count == 0:
    major = each

意味着，如果当前计数器为0，我们将当前遍历到的元素（each）赋值给候选主要元素（major）。这是因为当计数器为0时，表示之前遍历过的元素中没有一个元素的数量超过一半，所以我们需要用当前元素作为新的候选主要元素。

对抗阶段完成后，我们会得到一个候选主要元素。然后，在统计阶段，我们计算这个候选主要元素在列表中出现的次数。如果它的出现次数大于列表长度的一半，那么它就是主要元素，否则不存在主要元素。

这个算法的优点是时间复杂度为O(n)，空间复杂度为O(1)，在处理大数据时非常高效。