[已解决]新手求助-21讲课后作业

wohenhao123

有关摩尔投票法的代码没有看懂，可否详细讲解一下，谢谢
代码如下：
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("不存在主要元素。")

最佳答案

月排行榜 / 总排行榜

陶远航

2023-4-29 11:45:05

摩尔投票法（Moore Voting）是一种经典的算法，用于在一个序列中寻找出现次数超过一半的元素。它的核心思想是用两个变量来记录当前候选的元素和它的票数，遍历序列时如果当前元素和候选元素相同则将票数加一，否则将票数减一，当票数为零时则更换候选元素。由于出现次数超过一半的元素最多只有一个，因此在遍历完成后候选元素即为所求。

以下是摩尔投票法的详细讲解和代码解释：

对抗阶段：
在遍历整个序列之前，先初始化候选元素为序列的第一个元素，票数为零。

1. major = nums[0]
   
2. count = 0
   

复制代码

接下来遍历整个序列，如果当前元素和候选元素相同则将票数加一，否则将票数减一。如果票数减为零，则更换候选元素为当前元素。

1. for each in nums:
   
2.     if count == 0:
   
3.         major = each
   
4.     if each == major:
   
5.         count += 1
   
6.     else:
   
7.         count -= 1
   

复制代码

这样一遍遍历下来，就会找到序列中出现次数超过一半的元素。注意，由于候选元素可能是无效的，所以需要在遍历之前进行初始化。

统计阶段：
在对抗阶段结束后，候选元素即为出现次数超过一半的元素。此时再次遍历整个序列，统计候选元素出现的次数，如果超过了序列长度的一半，则说明找到了主要元素，否则说明不存在主要元素。

1. if nums.count(major) > len(nums) / 2:
   
2.     print("主要元素是：", major)
   
3. else:
   
4.     print("不存在主要元素。")
   
5. if nums.count(major) > len(nums) / 2:
   
6.     print("主要元素是：", major)
   
7. else:
   
8.     print("不存在主要元素。")
   

复制代码

完整代码如下：

1. nums = [2, 2, 4, 2, 3, 6, 2]
   
2. 
   
3. # 对抗阶段
   
4. major = nums[0]
   
5. count = 0
   
6. for each in nums:
   
7.     if count == 0:
   
8.         major = each
   
9.     if each == major:
   
10.         count += 1
    
11.     else:
    
12.         count -= 1
    
13. 
    
14. # 统计阶段
    
15. if nums.count(major) > len(nums) / 2:
    
16.     print("主要元素是：", major)
    
17. else:
    
18.     print("不存在主要元素。")
    

复制代码

对于给定的序列 [2, 2, 4, 2, 3, 6, 2]，运行上述代码会输出：

1. 主要元素是： 2
   

复制代码

跳转到最佳答案楼层

isdkz

这段代码实现了摩尔投票法（Boyer-Moore Majority Vote algorithm），用于在一个列表中找到主要元素（出现次数超过一半的元素）。代码分为两个阶段：对抗阶段和统计阶段。

1. 对抗阶段：

   这个阶段的目的是找到可能的主要元素。我们定义两个变量：`major` 和 `count`。`major` 用来记录当前候选主要元素，而 `count` 用来计算这个元素出现的次数。

   遍历列表中的每个元素：
   - 当 `count` 为 0 时，表示当前没有候选主要元素，我们将当前元素设置为候选主要元素，并将 `count` 设置为 1。
   - 如果当前元素等于候选主要元素，将 `count` 加 1。
   - 如果当前元素不等于候选主要元素，将 `count` 减 1。

   对抗阶段结束后，`major` 变量保存的是可能的主要元素。

2. 统计阶段：

   这个阶段的目的是验证对抗阶段找到的可能的主要元素是否真的是主要元素。我们计算 `major` 在列表中出现的次数，如果它的次数大于列表长度的一半，那么 `major` 就是主要元素。否则，列表中不存在主要元素。

这个算法的核心思想是，如果存在一个主要元素，那么它的出现次数一定超过其他所有元素出现次数之和。在对抗阶段，我们通过不断对消不同的元素对来找到可能的主要元素。在统计阶段，我们验证这个可能的主要元素是否满足主要元素的条件。

陶远航

摩尔投票法（Moore Voting）是一种经典的算法，用于在一个序列中寻找出现次数超过一半的元素。它的核心思想是用两个变量来记录当前候选的元素和它的票数，遍历序列时如果当前元素和候选元素相同则将票数加一，否则将票数减一，当票数为零时则更换候选元素。由于出现次数超过一半的元素最多只有一个，因此在遍历完成后候选元素即为所求。

以下是摩尔投票法的详细讲解和代码解释：

对抗阶段：
在遍历整个序列之前，先初始化候选元素为序列的第一个元素，票数为零。

1. major = nums[0]
   
2. count = 0
   

复制代码

接下来遍历整个序列，如果当前元素和候选元素相同则将票数加一，否则将票数减一。如果票数减为零，则更换候选元素为当前元素。

1. for each in nums:
   
2.     if count == 0:
   
3.         major = each
   
4.     if each == major:
   
5.         count += 1
   
6.     else:
   
7.         count -= 1
   

复制代码

这样一遍遍历下来，就会找到序列中出现次数超过一半的元素。注意，由于候选元素可能是无效的，所以需要在遍历之前进行初始化。

统计阶段：
在对抗阶段结束后，候选元素即为出现次数超过一半的元素。此时再次遍历整个序列，统计候选元素出现的次数，如果超过了序列长度的一半，则说明找到了主要元素，否则说明不存在主要元素。

1. if nums.count(major) > len(nums) / 2:
   
2.     print("主要元素是：", major)
   
3. else:
   
4.     print("不存在主要元素。")
   
5. if nums.count(major) > len(nums) / 2:
   
6.     print("主要元素是：", major)
   
7. else:
   
8.     print("不存在主要元素。")
   

复制代码

完整代码如下：

1. nums = [2, 2, 4, 2, 3, 6, 2]
   
2. 
   
3. # 对抗阶段
   
4. major = nums[0]
   
5. count = 0
   
6. for each in nums:
   
7.     if count == 0:
   
8.         major = each
   
9.     if each == major:
   
10.         count += 1
    
11.     else:
    
12.         count -= 1
    
13. 
    
14. # 统计阶段
    
15. if nums.count(major) > len(nums) / 2:
    
16.     print("主要元素是：", major)
    
17. else:
    
18.     print("不存在主要元素。")
    

复制代码

对于给定的序列 [2, 2, 4, 2, 3, 6, 2]，运行上述代码会输出：

1. 主要元素是： 2
   

复制代码