ptthon 摩尔投票法 疑问
nums =# 对抗阶段
major = nums
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，啊，别的位置的数字为啥不遍历啊??这一点不太清楚！我感觉就是major的值应该是得把nums中的所有元素都过一下！ {:10_266:}{:10_266:}{:10_266:}{:10_266:}孩子难受啊 for each in nums就是遍历
意思就是nums数组中的数字每一轮赋值给each
这个major = nums只是用来初始化major的 本帖最后由 翼是孤独 于 2022-1-21 15:24 编辑
摩尔投票法------------用来找出数组中出现超过一半的数字。
首先数组中随便选一个数作为“major”，（你这里是初始化成nums了）
设置一个计数器count = 0，用来标记major的数量
依次从数组中取数，如果取出的数和你的major相同，计数器就加1，如果不同，就抵消了，计数器-1
如果计数器减到0，就换一个major（因为既然和他不同的数能把它抵消完，它肯定没超过一半）
对了，上面说的有点问题，这个count最后的数值并不是major出现的次数，而是抵消完后还剩的major次数 翼是孤独 发表于 2022-1-21 14:32
for each in nums就是遍历
意思就是nums数组中的数字每一轮赋值给each
这个major = nums只是用来初始 ...
懂啦懂啦，还有一个问题就是，感觉最后的统计阶段很莫名其妙哎，感觉和上面没啥关系！上面的代码计算count的值有啥意义呢？ 本帖最后由 傻眼貓咪 于 2022-1-21 14:58 编辑
这是博耶-摩尔多数投票算法
major 初始值为第一个遍历元素（这里用位置 0 作为第一个开始遍历的元素，所以理所当然 major = nums。当然你也可以用其它元素作为开始遍历元素，但是每个元素只能遍历一次，为何不从 0 开始遍历呢？）nums =
# 对抗阶段
major = nums[-1] # 现在 major = 数组最后一个元素
count = 0
for each in nums[::-1]: # 从后面开始往前遍历
if count == 0:
major = each
count = 1
if each == major:
count += 1
else:
count -= 1
# 统计阶段
if nums.count(major) > len(nums) / 2:
print("主要元素是：", major)
else:
print("不存在主要元素。")结果一样 翼是孤独 发表于 2022-1-21 14:38
摩尔投票法------------用来找出数组中出现超过一半的数字。
首先数组中随便选一个数作为“major”，（你 ...
那如果出现负数的情况呢{:10_266:} muyang_zzF6 发表于 2022-1-21 14:42
那如果出现负数的情况呢
不会出现负数啊，你count归零的时候就会换major，major=each
然后紧接着的if each == major:是肯定成立的。
muyang_zzF6 发表于 2022-1-21 14:42
那如果出现负数的情况呢
明白了，不会出现负数！等到0的时候就不会再减少了，直接换major了，谢谢
{:10_254:} muyang_zzF6 发表于 2022-1-21 14:42
那如果出现负数的情况呢
统计阶段的话，是看题目需要
如果题中明确告诉你确实存在一个超过一半的数字，你最后是不需要统计的，直接输出major 就行
如果题中说可能存在，你这样求出的major 不一定是超过一半的数字
比如
最后major = 5
所以可能存在的话最后要统计一下，确保这个数字出现的个数确实 > 数组一半长度 major是为主要元素做标记的。并不是你想的那样去遍历整个列表
for each in nums: 中的each才是去遍历整个列表
major = nums#这句去掉都不影响
你代码for循环部分是找出出现最多次数的元素
找到列表中出现次数最多的元素之后，用cout()方法来得出出现了几次，然后看看是否满足主要元素的要求 楼主代码好像少了一行，当 count == 0:
major = each
count = 1 # 少了这行？ 翼是孤独 发表于 2022-1-21 14:48
统计阶段的话，是看题目需要
如果题中明确告诉你确实存在一个超过一半的数字，你最后是不需要统计的， ...
# 统计阶段
if nums.count(major) > len(nums) / 2:
print("主要元素是：", major)
else:
print("不存在主要元素。")
在对战阶段，会进行遍历一遍，但是到了统计阶段，直接统计major在nums中出现的次数，那这个被统计的major是哪个major呢？按理说应该是count数最高的那个major值，可又怎么确保输出的major是count数最高的那个值呢？ 傻眼貓咪 发表于 2022-1-21 15:01
楼主代码好像少了一行，当 count == 0:
major = each
count = 1 # 少了这行？
没有少吧{:10_257:}这是小甲鱼的代码哎
直接复制过来的 大马强 发表于 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
没有少吧这是小甲鱼的代码哎
直接复制过来的
好的{:10_257:} 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 ...
我想错了，我是在有主要元素前提考虑的
如果没有主要元素的话，那就不一定是出现次数最多的了{:10_278:} 大马强 发表于 2022-1-21 17:22
我想错了，我是在有主要元素前提考虑的
如果没有主要元素的话，那就不一定是出现次数最多的了
{:10_257:} 翼是孤独 发表于 2022-1-21 14:38
摩尔投票法------------用来找出数组中出现超过一半的数字。
首先数组中随便选一个数作为“major”，（你 ...
如果全部抵消后，后面又出现那个数字咋办？？、比如1,1,2,3,3,1，1里面1占一半，啊啊啊好难理解
页:
[1]
2