文章目錄

• 算法概述
• 題目
• • k=2
  • • 思路
    • 代碼
    • 復(fù)雜度分析
  • k=3
  • • 思路
    • 代碼
    • 復(fù)雜度分析

---

算法概述

摩爾投票算法經(jīng)常用于求眾數(shù)的題目，即，求 出現(xiàn)次數(shù)>n/k 的數(shù)，可以證明，出現(xiàn)次數(shù)超過 n/k 的數(shù)最多只有 k-1 個(gè)。否則必然違背「數(shù)總共只有 n 個(gè)」或者「當(dāng)前統(tǒng)計(jì)的是出現(xiàn)次數(shù)超過 n/k 的數(shù)」的前提條件。

• 我們可以設(shè)定 k-1 個(gè)變量來(lái)記錄最終結(jié)果。
• 以 k-1=3 為例，所求結(jié)果設(shè)為 k1、k2，用兩個(gè)變量 n1、n2 分別記錄 k1、k2 的出現(xiàn)次數(shù)。遍歷給定的數(shù)組 nums，設(shè) 當(dāng)前便利的到的元素為 nums[i] ，分情況處理：
• n1==0，此時(shí)需要更換 k1 ，k1=nums[i]。
• n2==0，此時(shí)需要更換 k2 ，k2=nums[i]。
• n1>0 且 nums[i]==k1，n1++。
• n2>0 且 nums[i]==k2，n2++。
• 不屬于以上四種情況則表明，n1>0 且 n2>0 且 nums[i]!=k1 且 nums[i]!=k1 ，即 nums[i] 不等于 k1 也不等于 k2，同時(shí) k1、k2 的出現(xiàn)次數(shù)大于 0，因此只需將兩者的出現(xiàn)次數(shù) -1 即可：n1--、n2-- 。

---

題目

k=2

數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

示例：

輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
輸出: 2

---

思路

用變量 x 代表要求的最終結(jié)果，也就是數(shù)組中的眾數(shù)。
用 sum 代表票數(shù)和。

推論一： 若記 眾數(shù) 的票數(shù)為 +1，非眾數(shù) 的票數(shù)為 -1，則一定有所有數(shù)字的 票數(shù)和 > 0。
推論二： 若數(shù)組的前 a 個(gè)數(shù)字的 票數(shù)和 = 0 ，則 數(shù)組剩余 (n-a) 個(gè)數(shù)字的 票數(shù)和一定仍 > 0 ，即后 (n-a) 個(gè)數(shù)字的 眾數(shù)仍為 x 。

第一條顯而易見，題目講的很清楚，最終要求的數(shù)出現(xiàn)的次數(shù)超過這組數(shù)字個(gè)數(shù)的二分之一，因此眾數(shù)個(gè)數(shù)大于非眾數(shù)。

第二條推論中，票數(shù)和=0 的情況代表著 這一段中眾數(shù)個(gè)數(shù)與非眾數(shù)個(gè)數(shù)相等，因此成立。

而我們不斷的割掉推論二中的 票數(shù)和=0的一段 ，具體做法是（上圖中黑字x）：每當(dāng) sum=0 時(shí)，此時(shí)將 x 更新為 下一段數(shù)字中的首元素，最終剩下的一段中的 x 即為我們所求的最終結(jié)果。

---

代碼

class Solution { public:int majorityElement(vector<int>& nums) {int sum = 0, x;for(int i = 0; i < nums.size(); i++){if(!sum) x = nums[i];sum += nums[i]==x?1:-1;}//加入了驗(yàn)證最終x是否大于數(shù)組長(zhǎng)度一半的操作//當(dāng)然在本題中是肯定的int count = 0;for(int& num:nums)if(num==x) count++;return count>nums.size()/2?x:-1;//當(dāng)無(wú)眾數(shù)時(shí)返回-1} };

---

復(fù)雜度分析

• 空間復(fù)雜度O(N)：遍歷數(shù)組。
• 時(shí)間復(fù)雜度O(1)：未開辟新空間。

---

k=3

給定一個(gè)大小為 n 的整數(shù)數(shù)組，找出其中所有出現(xiàn)超過 ? n/3 ? 次的元素。（LC題目鏈接）

示例：

輸入： [3,2,3]
輸出： [3]

---

思路

如果兩個(gè)人的票數(shù)都超過了三分之一，剩余的票就不到三分之一了，因此最多有兩個(gè)超過 n/3 的元素。

---

代碼

class Solution { public:vector<int> majorityElement(vector<int>& nums) {// 如果兩個(gè)人的票數(shù)都超過了三分之一，剩余的票就不到三分之一了// 因此最多有兩個(gè)超過n/3的元素，摩爾投票法vector<int> v;int n1 = 0, n2 = 0, a = 0, b = 0;for(auto i:nums){if(n1>0 && i==a) n1++;else if(n2>0 && i==b) n2++;else if(n1==0){a=i;n1=1;}else if(n2==0){b=i;n2=1;}else{n1--;n2--;}//cout << a << " " << n1 << " " << b << " " << n2 << endl;}int cnt1 = 0, cnt2 = 0;for(auto i:nums){if(n1>0 && i==a) cnt1++;if(n2>0 && i==b) cnt2++;}if(cnt1>nums.size()/3) v.push_back(a);if(cnt2>nums.size()/3) v.push_back(b);return v;} };

---

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)：其中 n 為數(shù)組的長(zhǎng)度。
• 空間復(fù)雜度：O(1)：只需要常數(shù)個(gè)元素用來(lái)存儲(chǔ)關(guān)鍵元素和統(tǒng)計(jì)次數(shù)即可。

總結(jié)

以上是生活随笔為你收集整理的Boyer-Moore 投票算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。