[已解决]ptthon 摩尔投票法 疑问

muyang_zzF6

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("不存在主要元素。")

这个代码里边为啥只有 major = num[0]，啊，别的位置的数字为啥不遍历啊??这一点不太清楚！我感觉就是major的值应该是得把nums中的所有元素都过一下！

最佳答案

月排行榜 / 总排行榜

翼是孤独

2022-1-21 14:38:28

摩尔投票法------------用来找出数组中出现超过一半的数字。
首先数组中随便选一个数作为“major”，（你这里是初始化成nums[0]了）
设置一个计数器count = 0，用来标记major的数量
依次从数组中取数，如果取出的数和你的major相同，计数器就加1，如果不同，就抵消了，计数器-1
如果计数器减到0，就换一个major（因为既然和他不同的数能把它抵消完，它肯定没超过一半）


对了，上面说的有点问题，这个count最后的数值并不是major出现的次数，而是抵消完后还剩的major次数

跳转到最佳答案楼层

muyang_zzF6

孩子难受啊

翼是孤独

for each in nums就是遍历
意思就是nums数组中的数字每一轮赋值给each
这个major = nums[0]只是用来初始化major的

翼是孤独

摩尔投票法------------用来找出数组中出现超过一半的数字。
首先数组中随便选一个数作为“major”，（你这里是初始化成nums[0]了）
设置一个计数器count = 0，用来标记major的数量
依次从数组中取数，如果取出的数和你的major相同，计数器就加1，如果不同，就抵消了，计数器-1
如果计数器减到0，就换一个major（因为既然和他不同的数能把它抵消完，它肯定没超过一半）


对了，上面说的有点问题，这个count最后的数值并不是major出现的次数，而是抵消完后还剩的major次数

muyang_zzF6

翼是孤独 发表于 2022-1-21 14:32
for each in nums就是遍历
意思就是nums数组中的数字每一轮赋值给each
这个major = nums[0]只是用来初始 ...

懂啦懂啦，还有一个问题就是，感觉最后的统计阶段很莫名其妙哎，感觉和上面没啥关系！上面的代码计算count的值有啥意义呢？

傻眼貓咪

这是博耶-摩尔多数投票算法
major 初始值为第一个遍历元素（这里用位置 0 作为第一个开始遍历的元素，所以理所当然 major = nums[0]。当然你也可以用其它元素作为开始遍历元素，但是每个元素只能遍历一次，为何不从 0 开始遍历呢？）

1. nums = [2, 2, 4, 2, 3, 6, 2]
   
2.    
   
3. # 对抗阶段
   
4. major = nums[-1] # 现在 major = 数组最后一个元素
   
5. count = 0
   
6. for each in nums[::-1]: # 从后面开始往前遍历
   
7.     if count == 0:
   
8.         major = each
   
9.         count = 1
   
10.     if each == major:
    
11.         count += 1
    
12.     else:
    
13.         count -= 1
    
14.    
    
15. # 统计阶段
    
16. if nums.count(major) > len(nums) / 2:
    
17.     print("主要元素是：", major)
    
18. else:
    
19.     print("不存在主要元素。")

复制代码

结果一样

muyang_zzF6

翼是孤独 发表于 2022-1-21 14:38
摩尔投票法------------用来找出数组中出现超过一半的数字。
首先数组中随便选一个数作为“major”，（你 ...

那如果出现负数的情况呢

翼是孤独

muyang_zzF6 发表于 2022-1-21 14:42
那如果出现负数的情况呢

不会出现负数啊，你count归零的时候就会换major，major=each
然后紧接着的if each == major:是肯定成立的。

muyang_zzF6

muyang_zzF6 发表于 2022-1-21 14:42
那如果出现负数的情况呢

明白了，不会出现负数！等到0的时候就不会再减少了，直接换major了，谢谢

翼是孤独

muyang_zzF6 发表于 2022-1-21 14:42
那如果出现负数的情况呢

统计阶段的话，是看题目需要
如果题中明确告诉你确实存在一个超过一半的数字，你最后是不需要统计的，直接输出major 就行

如果题中说可能存在，你这样求出的major 不一定是超过一半的数字

比如[1,2,3,4,5]
最后major = 5
所以可能存在的话最后要统计一下，确保这个数字出现的个数确实 > 数组一半长度

大马强

major是为主要元素做标记的。并不是你想的那样去遍历整个列表
for each in nums: 中的each才是去遍历整个列表

1. major = nums[0]  #这句去掉都不影响

复制代码

你代码for循环部分是找出出现最多次数的元素
找到列表中出现次数最多的元素之后，用cout()方法来得出出现了几次，然后看看是否满足主要元素的要求

傻眼貓咪

楼主代码好像少了一行，当 count == 0:
major = each
count = 1 # 少了这行？

muyang_zzF6

翼是孤独 发表于 2022-1-21 14:48
统计阶段的话，是看题目需要
如果题中明确告诉你确实存在一个超过一半的数字，你最后是不需要统计的， ...

1. # 统计阶段
   
2. if nums.count(major) > len(nums) / 2:
   
3.     print("主要元素是：", major)
   
4. else:
   
5.     print("不存在主要元素。")

复制代码

在对战阶段，会进行遍历一遍，但是到了统计阶段，直接统计major在nums中出现的次数，那这个被统计的major是哪个major呢？按理说应该是count数最高的那个major值，可又怎么确保输出的major是count数最高的那个值呢？

muyang_zzF6

傻眼貓咪 发表于 2022-1-21 15:01
楼主代码好像少了一行，当 count == 0:
major = each
count = 1 # 少了这行？

没有少吧这是小甲鱼的代码哎
直接复制过来的

muyang_zzF6

大马强 发表于 2022-1-21 14:55
major是为主要元素做标记的。并不是你想的那样去遍历整个列表
for each in nums: 中的each才是去遍历整个 ...

在对战阶段，会进行遍历一遍，但是到了统计阶段，直接统计major在nums中出现的次数，那这个被统计的major是哪个major呢？按理说应该是count数最高的那个major值，可又怎么确保输出的major是count数最高的那个值呢？

傻眼貓咪

muyang_zzF6 发表于 2022-1-21 15:06
没有少吧这是小甲鱼的代码哎
直接复制过来的

好的

翼是孤独

muyang_zzF6 发表于 2022-1-21 15:05
在对战阶段，会进行遍历一遍，但是到了统计阶段，直接统计major在nums中出现的次数，那这个被统计的m ...

摩尔投票法原理就是
把不重复的数两两抵消，如果你当前的major 的count 能被抵消成0，就肯定说明你的major 不能把和他不同的数抵消掉啊

可疑这样理解，你把当前major 和 数组中别的数字看作两军，1v1抵消，如果major 不能杀光剩余所有数字，它出现的次数肯定没超过一半。

大马强

muyang_zzF6 发表于 2022-1-21 15:07
在对战阶段，会进行遍历一遍，但是到了统计阶段，直接统计major在nums中出现的次数，那这个被统计的major ...

我想错了，我是在有主要元素前提考虑的
如果没有主要元素的话，那就不一定是出现次数最多的了

muyang_zzF6

大马强 发表于 2022-1-21 17:22
我想错了，我是在有主要元素前提考虑的
如果没有主要元素的话，那就不一定是出现次数最多的了

lolin.201903

翼是孤独 发表于 2022-1-21 14:38
摩尔投票法------------用来找出数组中出现超过一半的数字。
首先数组中随便选一个数作为“major”，（你 ...

如果全部抵消后，后面又出现那个数字咋办？？、比如1,1,2,3,3,1，1里面1占一半，啊啊啊好难理解