[已解决]课后作业代码解读

LEEFEI571

我在做小甲鱼老师关于列表的课后作业,其中有一道题是这样的:

1. 其实上面这道题有一个经典的解法，就是使用摩尔投票法（Boyer–Moore majority vote）。
摩尔投票法有时候也被称为“多数投票法”，该算法解决的问题是如何在任意多的候选人中（选票无序），找到获得票数最多的那个。
摩尔投票法分为两个阶段：
•        对抗阶段：分属两个候选人的票数进行两两对抗抵消
•        计数阶段：计算对抗结果中最后留下的候选人票数是否有效

大家不妨可以将摩尔投票法的工作原理想象为诸侯争霸，假设每个国家都是全民皆兵，并且打起仗来都是以 1 换 1 的形式消耗人口，当一个国家人口总数为 0，那么 Gameover，OK，如果某国人口数量超过所有国家总人口的一半，最终赢家就肯定是它。

本体代码答案如下:
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("不存在主要元素。")

这道题的代码我解读不明白,尤其是for语句项下的if及else分支语句都是在判断些什么,烦请大神帮忙解读一下,感谢感谢!

最佳答案

月排行榜 / 总排行榜

jackz007

2024-12-8 23:33:51

       这个题的思路是，设置一个主元素变量 major 及其计数器 count，用变量 each 循环遍历 nums[] 中的每一个元素，当 count 为 0 时，把 each 设置为 major，同时，count 置 1；当 count > 0  时，分两种情况，如果 each 与 major 相同，则 count + 1，否则，count - 1，到 count = 0 时，major 重新赋值。很显然，正常情况下，一个 major 如果能坚持到最后（count 不被归 0），其数量应该超过 nums[] 元素的一半，这就是存在主要元素的情况。当然，这样统计也不能排除某一个仅仅具有相对数量优势的元素也有可能成为 major，但是，其数量并不足以超过 nums[] 元素的一半，像这种就属于 "不存在主要元素。" 的情况。
        其实，这道题的代码可以更加简单：

1. nums = [2, 2, 4, 2, 3, 6, 2]
   
2. nums . sort()
   
3. print("主要元素是：", nums[len(nums) // 2]) if nums . count(nums[len(nums) // 2]) > len(nums) // 2 else print("不存在主要元素。")

复制代码

        其思路为：对 nums[] 按照数值从小到大的顺序排序，如果 nums[] 有主要元素，其位置一定在新 nums[] 的中间部位，其数量应该超过 nums[] 元素的一半。

      

跳转到最佳答案楼层

FishC

1. nums =
   
2. 
   
3. # 对抗阶段
   
4. major = nums
   
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("不存在主要元素。")

复制代码

上述代码的解读如下：

1. **对抗阶段**：
   - `major = nums` 是初始化一个变量来表示当前假设的主要元素（占多数的元素）。
   - `count = 0` 初始化计数器。
   - `for each in nums:` 遍历列表中的每个元素。
   - `if count == 0:` 如果计数器为 0，说明当前没有确定主要元素，将当前元素假设为主要元素，`major = each`。
   - `if each == major:` 如果当前元素 `each` 等于主要元素 `major`，说明遇到了相同的元素，增加计数器 `count += 1`。
   - `else:` 如果当前元素 `each` 不等于主要元素，说明遇到了不同的元素，减少计数器 `count -= 1`。这种情况下，抵消一个相同的票数和一个不同的票数。

2. **统计阶段**：
   - `if nums.count(major) > len(nums) / 2:` 统计 `major` 在数组中的出现次数，如果出现次数大于数组长度的一半，说明 `major` 是主要元素。
   - `print("主要元素是：", major)` 打印主要元素。
   - `else:` 如果 `major` 出现的次数不大于数组长度的一半，说明不存在主要元素。
   - `print("不存在主要元素。")` 打印不存在主要元素的信息。

这个算法通过抵消原则简化了寻找主要元素的过程，将时间复杂度降低到 O(n)。希望这个解读能帮助你理解这段代码的工作原理！如果还有问题，请随时问我。

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

jackz007

       这个题的思路是，设置一个主元素变量 major 及其计数器 count，用变量 each 循环遍历 nums[] 中的每一个元素，当 count 为 0 时，把 each 设置为 major，同时，count 置 1；当 count > 0  时，分两种情况，如果 each 与 major 相同，则 count + 1，否则，count - 1，到 count = 0 时，major 重新赋值。很显然，正常情况下，一个 major 如果能坚持到最后（count 不被归 0），其数量应该超过 nums[] 元素的一半，这就是存在主要元素的情况。当然，这样统计也不能排除某一个仅仅具有相对数量优势的元素也有可能成为 major，但是，其数量并不足以超过 nums[] 元素的一半，像这种就属于 "不存在主要元素。" 的情况。
        其实，这道题的代码可以更加简单：

1. nums = [2, 2, 4, 2, 3, 6, 2]
   
2. nums . sort()
   
3. print("主要元素是：", nums[len(nums) // 2]) if nums . count(nums[len(nums) // 2]) > len(nums) // 2 else print("不存在主要元素。")

复制代码

        其思路为：对 nums[] 按照数值从小到大的顺序排序，如果 nums[] 有主要元素，其位置一定在新 nums[] 的中间部位，其数量应该超过 nums[] 元素的一半。