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

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[] 元素的一半。

      

跳转到最佳答案楼层