溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇“c++中摩爾投票法如何使用”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“c++中摩爾投票法如何使用”文章吧。
算法：
典型的摩爾投票法使用場景
摩爾投票法分為兩個階段：抵消階段和計數階段。
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++中摩爾投票法如何使用”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
