c++中摩尔投票法如何使用
这篇“c++中摩尔投票法如何使用”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“c++中摩尔投票法如何使用”文章吧。
成都创新互联公司主要从事成都网站制作、成都网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务耿马,10余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575
算法：
典型的摩尔投票法使用场景
摩尔投票法分为两个阶段：抵消阶段和计数阶段。
1. 抵消阶段：两个不同投票进行对坑，并且同时抵消掉各一张票，如果两个投票相同，则累加可抵消的次数；2. 计数阶段：在抵消阶段最后得到的抵消计数只要不为0，那这个候选人是有可能超过一半的票数的， 为了验证，则需要遍历一次，统计票数，才可确定。 备注：对于1/3，1/4.....1/n，做法就是设置n-1个投票候选人，采用摩尔投票的方法进行操作。
题目1: 超过半数的多数元素
代码实现：
func majorityElement(nums []int) int { tmp,count := 0,0 for _,num:=range nums { if count == 0 { tmp = num } if num == tmp { count++ } else { count-- } } return tmp}// 算法：数组里面有一个数超过一半数量，// 那么可以用这个数作为标示，这个数就+1，不是这个数就-1，最后剩余的数就是所求 题目2: 求众数
代码实现：
func majorityElement(nums []int) []int {// 创建返回值var res = make([]int, 0)if nums == nil || len(nums) == 0 {return res}// 初始化两个候选人 candidate，以及他们的计数票cand1 := nums[0]count1 := 0cand2 := nums[0]count2 := 0//摩尔投票法// 配对阶段for _, num := range nums {// 投票if cand1 == num {count1++continue}if cand2 == num {count2++continue}if count1 == 0 {cand1 = numcount1++continue}if count2 == 0 {cand2 = numcount2++continue}count1--count2--}// 计数阶段count1 = 0count2 = 0for _, num := range nums {if cand1 == num {count1++} else if cand2 == num {count2++}}if count1 > len(nums)/3 {res = append(res, cand1)}if count2 > len(nums)/3 {res = append(res, cand2)}return res}// 算法：摩尔投票法的应用// 因为是1/3,所以采用2个候选人来进行抉择。
以上就是关于“c++中摩尔投票法如何使用”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注创新互联行业资讯频道。
网页标题：c++中摩尔投票法如何使用
当前路径：http://6mz.cn/article/piigdi.html