?

?

友友們 大家好 我是你們的小王同學

?

今天給大家帶來兩道經典的摩爾投票算法的題型? 如果覺得小王寫的不錯 麻煩給個三連啦、

小王的csdn主頁：(4條消息) 學好c語言的小王同學的博客_CSDN博客-c語言,力扣刷題領域博主

?

小王的gitee：

比特王信哲 (bitewang) - Gitee.com

?

????????目錄

? ? ? ? ??1.什么是摩爾投票法?

?2.例題?

? ? ? ??169 多數元素

? ? ? ? ?題目要求?：

? ? ? ? ?解題思路：?

? ? ? ??源碼附上：?

1710.主要元素?

? ? ???題目描述：

? ? ? ??源碼附上：?

1.什么是摩爾投票法

?

---

在?個?序數組中，存在?個數，它出現的次數?于數組長

度的?半。輸出這個數
?、排序、遍歷
?、摩爾投票法
摩爾投票算法是?種使?線性時間和常數空間查找?部分元素序列的算法。
最簡單的形式就是，查找輸?中重復出現超過?半以上(必須?于n/2，等于不算)的元素。如果序列中沒有這種元素，算法不能檢測到正確結
果，將輸出其中的?個元素之?。
如果不能保證輸?數據中有占有?半以上的元素，需要再遍歷?下驗證。
滿?兩個先決條件
1、出現超過?半以上(n/2)的元素有且只有?個；
2、這個元素?定存在
算法步驟
我們維護?個局部變量作為當前查找元素，?個局部變量作為計數器，
當遍歷開始的時候，此時計數（count）為0，則將數組第?個元素作為當前查找元素；
當遍歷的元素與查找元素相等，計數加1；反之則-1；
若當計數為0時，將下?個元素作為當前查找元素，繼續重復以上操作；當遍歷結束時，當前查找元素則為?標元素
?

?

?

?摩爾投票法分為兩個核心步驟

?投票階段：投票人之間票數進行抵消

計數階段：計算對抗結果最后剩下的那個候選人的票數是否有效

?2.例題

題目來自LeetCode

169 多數元素

題目要求?：

169. 多數元素 - 力扣（LeetCode） (leetcode-cn.com)

解題思路：?

1.我們先定義一個候選人 就是數組的第一個元素

2.然后定義一個記錄候選人次數的count 初始化count

3.然后for循環遍歷 如果有候選人那么我們的count就++，反之則- -

4.如果count為0時，就更換候選人

?

源碼附上：?

class Solution {public int majorityElement(int[] nums) {int len=nums.length;int major=nums[0];//遍歷第一個元素，候選人是2int count=0;for(int i=0;i<len;i++){//如果數組中還有2的話我們的count就++；if(nums[i]==major){count++;}else{//如果沒有就減1count--;}//如果count=0的時候就更換候選人if(count==0){//更換候選人major=nums[i];//重新賦值major//票數重置為1count=1;}}return major;} }

這種情況只能對于多數存在的情況下 比如[4,5,6]major等于6顯然是錯誤的?

所以對于不一定存在多數的情況下 我們需要在求出major的情況下 在遍歷一遍?

統計count的次數是否大于數組長度的一半

?1710.主要元素

?題目描述：

源碼附上：?

class Solution {public int majorityElement(int[] nums) {int len=nums.length;int major=nums[0];//遍歷第一個元素，候選人是2int count=0;for(int i=0;i<len;i++){if(count==0){//更換候選人major=nums[i];//重新賦值major//票數重置為1}//如果數組中還有2的話我們的count就++；if(major==nums[i]){count++;}else{//如果沒有就減1count--;}//如果count=0的時候就更換候選人}count=0;for(int num:nums){ //遍歷一遍 記錄count的次數if(num==major){count++;}}return(count<=len/2)?-1:major; //根據條件判斷如果長度超過數組長度的一半 就輸出major反之則輸出-1} }

?以上就是小王同學給大家帶來的兩道經典的摩爾投票法的例題

友友們如果覺得小王寫的不錯就三連支持一下啦

碼字不易 謝謝大家

總結

以上是生活随笔為你收集整理的力扣刷题篇——摩尔投票算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。