[已解决]第21讲和22讲 摩尔投票法

gainer

摩尔投票法（Boyer–Moore majority vote）
摩尔投票法分为两个阶段：

对抗阶段：分属两个候选人的票数进行两两对抗抵消
计数阶段：计算对抗结果中最后留下的候选人票数是否有效

对于习题给出的情况
nums = [2, 2, 4, 2, 3, 6, 2]
对抗算法部分不是很理解

我理解 这里 候选人是1# 2# 3#……6#……
nums中是投票人投出的候选人序号，

也就是7个投票人给至少6个候选人投票
这里对抗阶段过程，我认为应该是
第一步 针对每个有票数的候选人，先去掉1票
得到[2,  2, 2]
此时 2号候选人已经胜出

而习题答案中，
2和4抵消，2又和3抵消 2在和6抵消
那么适用的是怎么样的投票情况呢？
不是很理解

最佳答案

月排行榜 / 总排行榜

FishC

2024-12-27 08:14:45

摩尔投票法的核心思想是通过两两抵消来逐步筛选出可能的多数元素。这里的问题中，`nums` 是一个投票结果的数组，其中每个数字代表一个投票给某个候选人的票数。我们需要识别出可能的多数候选人。下面是摩尔投票法的对抗阶段的简化步骤：

1. **初始化**：设定第一个候选人为 `candidate`，计数器 `count` 为 1。
2. **遍历数组**：
   - 如果 `count` 为 0，则将当前数值设为新的 `candidate`，并将 `count` 重置为 1。
   - 如果当前数值等于 `candidate`，增加 `count`。
   - 如果当前数值不等于 `candidate`，减少 `count`。
3. **结果**：经过遍历后，`candidate` 就是可能的多数元素。

在你的习题中，比如候选人编号为 2、4、3、6 等，每一次遍历一个新的候选号码就分别和当前 `candidate` 比较，根据上述规则进行抵消或计数调整。这并不是去掉每个候选人的一票，而是基于当前位置的投票结果进行两两抵消。

让我们具体来看对抗阶段的过程：

- 初始 `candidate` 是 `2`，`count` 是 1。
- 下一个数字是 `4`，与 `2` 不同，`count` 减少至 0。
- `count` 为 0，`candidate` 设为 `3`，`count` 重置为 1。
- 下一个数字是 `6`，与 `3` 不同，`count` 减少至 0。
  
按此顺序进行，最终留在 `candidate` 的就是可能的多数候选人。接下来通过计数阶段，验证这个元素的真正票数是否大于一半。

希望这能帮助你理解摩尔投票法的对抗阶段。如果还有疑问，可以进一步提问！

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

跳转到最佳答案楼层

FishC

摩尔投票法的核心思想是通过两两抵消来逐步筛选出可能的多数元素。这里的问题中，`nums` 是一个投票结果的数组，其中每个数字代表一个投票给某个候选人的票数。我们需要识别出可能的多数候选人。下面是摩尔投票法的对抗阶段的简化步骤：

1. **初始化**：设定第一个候选人为 `candidate`，计数器 `count` 为 1。
2. **遍历数组**：
   - 如果 `count` 为 0，则将当前数值设为新的 `candidate`，并将 `count` 重置为 1。
   - 如果当前数值等于 `candidate`，增加 `count`。
   - 如果当前数值不等于 `candidate`，减少 `count`。
3. **结果**：经过遍历后，`candidate` 就是可能的多数元素。

在你的习题中，比如候选人编号为 2、4、3、6 等，每一次遍历一个新的候选号码就分别和当前 `candidate` 比较，根据上述规则进行抵消或计数调整。这并不是去掉每个候选人的一票，而是基于当前位置的投票结果进行两两抵消。

让我们具体来看对抗阶段的过程：

- 初始 `candidate` 是 `2`，`count` 是 1。
- 下一个数字是 `4`，与 `2` 不同，`count` 减少至 0。
- `count` 为 0，`candidate` 设为 `3`，`count` 重置为 1。
- 下一个数字是 `6`，与 `3` 不同，`count` 减少至 0。
  
按此顺序进行，最终留在 `candidate` 的就是可能的多数候选人。接下来通过计数阶段，验证这个元素的真正票数是否大于一半。

希望这能帮助你理解摩尔投票法的对抗阶段。如果还有疑问，可以进一步提问！

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

gainer

看来是我没get到摩尔投票法的精髓
我再研究一下

FishC

gainer 发表于 2024-12-27 17:32
看来是我没get到摩尔投票法的精髓
我再研究一下

好的，摩尔投票法初学时确实有些抽象，多研究一下会更清晰。总之，它主要是通过在遍历中逐步消减不同的投票来筛选出一个可能的多数值。理解其中的逻辑，可以帮助你解决很多类似的多数计数问题。如果有需要，可以随时来问，我会很乐意帮助你进一步理解！加油！

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