摩爾投票算法( Boyer-Moore Voting Algorithm)

update：21/07/24

前言

絕對衆數。在數列 \(p\) 中出現次數嚴格大于 \(\frac{\vert p \vert}{2}\) 的數叫做絕對衆數。

快速排序

一般來說我們可以直接排序解決問題，如果存在絕對衆數的話，最中間的數一定是絕對衆數。

時間複雜度為 \(\mathcal{O}(n\ log n)\)

摩爾投票算法

摩爾投票法的基本思想很容易了解，在每一輪投票過程中，從數組中找出一對不同的元素，将其從數組中删除。循環執行這一操作，直到無法再進行投票，如果數組為空，則沒有任何元素出現的次數超過該數組長度的一半（無絕對衆數）。如果隻存在一種元素，那麼這個元素則可能為絕對衆數。

在編寫算法的過程中，我們可以直接按照數組原來的順序進行投票，删除。

具體實作：設 \(num\) 為目前出現階段超過半數的元素（候選數），\(cnt\) 為此元素出現次數。由于有了階段的概念，這其實這也是一種動态規劃思想。

一開始 \(num\) 直接為數組第一個元素，\(cnt = 1\)。（原因是隻有一個元素的數組，唯一的那個元素一定是絕對衆數）

接着周遊數列 \(p\)，設目前數為 \(k\) .

• 若 \(k = num\)，則 \(cnt + 1\)。
• 若 \(k \not = num\)，則我們可以把目前候選數和目前數同時删除，具體操作就是讓 \(cnt - 1\)，這樣就相當于忽略了數 \(k\)，删去一個 \(num\)。
• 若 \(cnt = 0\)，表明前一階段并沒有出現次數超過半數的元素。假設絕對衆數存在，那麼絕對衆數一定在剩餘的數組中是絕對衆數，這樣我們隻需要求解原始問題的子問題即可，即在後一階段的絕對衆數是多少。回到開始， \(num\) 為目前元素，\(cnt = 1\)。

最終，若 \(cnt > 0\)，則 \(num\) 可能為候選元素。掃一遍數組确認一下即可。

複雜度為線性的，\(O(n)\)。

void majorityElement(vector<int>& p) {  
    int num = -1, cnt = 0;
    for(int i = 0; i < p.size(); ++i) {
        if(cnt == 0) num = p[i], cnt++;
        else if(p[i] == num) cnt++;
        else cnt--;        
    }
    cnt = 0;
    for(int i = 0; i < p.size(); ++i)
        if(p[i] == num) cnt++;
    if(cnt > p.size() / 2) printf("Found: %d\n", num);
    else printf("Not Found\n");
}
           

摩爾投票算法的改進：

1，題目： LeetCode 229 [Majority Element II]

給定一個整型數組，找到所有主元素，它在數組中的出現次數嚴格大于數組元素個數的三分之一。

算法：每次删除三個不相同的數，最後留下的一定是出現次數超過1/3的數，這個思想可以推廣到出現次數超過1/k次的元素有哪些。

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> re;
        if (nums.size()==0) return re;
        int candidate1 = 0;
        int count1 = 0;
        int candidate2 = 0;
        int count2 = 0;
        for (int i=0; i<nums.size(); i++) {
            if (nums[i] == nums[candidate1]) count1++;
            else if (nums[i] == nums[candidate2]) count2++;
            else if (count1==0) {
                candidate1 = i;
                count1 = 1;
            }
            else if (count2==0) {
                candidate2 = i;
                count2 = 1;
            }
            else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int i=0; i<nums.size(); i++) {
            if (nums[i] == nums[candidate1]) count1++;
            else if (nums[i] == nums[candidate2]) count2++;
        }
        if (count1 > nums.size()/3) re.push_back(nums[candidate1]);
        if (count2 > nums.size()/3) re.push_back(nums[candidate2]);
        return re;
    }
};