21讲的摩尔计数法

TJ0929

# 对抗阶段

major = nums[0]

count = 0

for each in nums:

    if count == 0:

        major = each

    if each == major:

        count += 1

    else:

        count -= 1

@FishC 实在没看懂这个对抗阶段怎么理解，可以求助一下吗，谢谢

FishC

当然可以！让我来解释一下摩尔计数法的对抗阶段。

摩尔计数法主要用于在一个数组中寻找可能出现次数超过一半的元素，具体实现如下：

1. 初始化候选元素 major 为数组中的第一个元素，并设置计数器 count 为 0。
2. 遍历整个数组，对于每一个元素，看它是否和当前候选元素 major 相同：
   - 如果相同，则计数器 count 加 1。
   - 如果不同，则计数器 count 减 1。
3. 当计数器变为 0 时，重新选择下一个元素作为候选元素 major，并重置计数器 count 为 1。

这个过程通过相互抵消的方式，使得最终剩下来的候选元素就是可能的众数。

下面是代码的解释：

major = nums    # 假设第一个元素为候选
count = 0       # 初始化计数器为 0

for each in nums:      # 遍历数组中的每一个元素
    if count == 0:     # 若计数器为 0，则选择当前元素为新的候选
        major = each
    if each == major:  # 若当前元素与候选相同，则计数器加 1
        count += 1
    else:              # 若当前元素与候选不同，则计数器减 1
        count -= 1

希望这个解释能够帮助你理解摩尔计数法的对抗阶段。如果还有问题，请随时提问！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

TJ0929

@FishC 可以回答一下这个问题吗，谢谢！

FishC

TJ0929 发表于 2025-02-21 18:52
@FishC 可以回答一下这个问题吗，谢谢！

当然可以！请问有什么问题需要解答呢？

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

小甲鱼的二师兄

算法的核心思想是 “对抗”，即：

• 通过投票的方式，让不同的元素相互抵消（对抗）。
• 在遍历数组的过程中，始终保留一个候选 major，如果遇到相同元素就增加计数，遇到不同元素就减少计数。
• 最终剩下的 major 就是众数。
  

major = nums[0]  # 先假设第一个元素是众数
count = 0  # 计数器初始化为 0

for each in nums:  # 遍历整个数组
    if count == 0:  # 如果计数为 0，更新候选众数
        major = each  # 重新选择当前元素作为候选

    if each == major:  # 如果当前元素等于候选众数
        count += 1  # 计数增加
    else:  # 如果当前元素不同
        count -= 1  # 计数减少

对抗阶段的理解：

• 计数 count 代表当前候选 major 的“支持度”，如果 count == 0，说明之前的候选已经被“对抗”掉了，需要重新选择新的候选。
• 如果当前元素和 major 相同，说明这个元素在“支持” major，于是 count +1。
• 如果当前元素和 major 不同，说明它在“反对” major，于是 count -1。
• 如果 count 归零，说明 major 遭到了足够多的“反对”，于是换一个新的候选。