摘要：，這是最基礎的最大投票算法。例如，和這兩個數(shù)組最后得到的分別為和，但是這并不影響答案的正確性。接下來，我們可以對這個算法做一些簡單的擴展，我們當前定義的的數(shù)量大于的元素。為當前出現(xiàn)的次數(shù)。這意味著當前這個數(shù)字就是這兩個等待的第三個數(shù)字。

Boyer-Moore：A Linear Time Majority Vote Alogrithm，這是最基礎的最大投票算法。

原文中提到：decides which element of a sequence is in the majority, provided there is such an element.,但是講的有一些含糊。我再補充一下：在一次投票中，如果某一種投票出現(xiàn)的數(shù)量大于（這里必須是大于而不能是等于，否則在某些特殊條件下會得到錯誤結果）總投票，我們就認為這種投票是我們要找的 Majority Element。

參考 Leetcode 上的這道題：169.Majority Element

Given an array of size n, find the Majority Element. The Majority Element is the element that appears more than ? n/2 ? times.
You may assume that the array is non-empty and the Majority Element always exist in the array.

算法的具體思路是：假設在給定長度為 n 的數(shù)組中，Majority Element 出現(xiàn)的次數(shù)是 k 次，那么非 Majority Element 的出現(xiàn)次數(shù)就為 n-k。如果我們能去掉這 n-k 個元素那么剩下的就全部是 Majority Element 了。

我們可以遍歷數(shù)組,當碰到兩個不一樣的數(shù)字時,我們將這兩個數(shù)字同時丟棄這兩個數(shù)字中可能有一個為 Majority Element,也可能兩個都不為Majority Element.因為k 大于 n/2,所以在最差情況下(每次移除不同數(shù)字時都包含一個Majority Element),我們仍然能夠保證最后得到的數(shù)字是Majority Element.

在網(wǎng)上看到的很多資料中，對這一步的解釋都是略微有些問題的。很多人簡單的將這一步解釋為：找到一個Majority Element，隨后找到一個 非Majority Element，并將他們一并移除，這其實是錯誤的。我們在循環(huán)的時候，并沒有辦法判定當前的數(shù)字是否為 Majority Element，所以在移除的時候，我們可能是移除了一個 Majority Element 和一個 非Majority Element，也有可能移除的是兩個非Majority Element。所以最后 count 的值是不確定的，但是它能夠保證在最差情況下，剩余的仍然是 Majority Element。例如，[1,2,3,3,3] 和 [1,3,2,3,3] 這兩個數(shù)組最后得到的 count 分別為 3 和 1，但是這并不影響答案的正確性。

這也是前面提到的Majority Element的數(shù)量必須大于n/2的原因.

很容易算出最后剩余的Majority Element個數(shù)最少為： n - ((n - k) + (n - k)) = 2k - n。

public class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        for(int i = 0,count = 0; i < nums.length; i++){
            //問題一： if 的判定順序有要求嗎？如果有要求的話應該是怎么樣的呢？
            if(count == 0){
                count++;
                candidate = nums[i];
            }else if(candidate != nums[i]){
                count--;
            }else{
                count++;
            }
        }
        return candidate;
    }
}

這個算法很經典，也很簡單，畢竟不用自己想。

接下來，我們可以對這個算法做一些簡單的擴展，我們當前定義的 Majority Element 的數(shù)量大于 n/2 的元素。

如果我們在投票只要滿足投票數(shù)量超過 n/3 即認為它是最大投票，我們能不能求出這個值呢？

媽蛋，文章中這種問題就跟小說里主角跳崖會不會死一樣，有標準答案的。
喬治啊啊馬丁：？

最大投票資料片：熊貓人之謎 229. Majority Element II

Given an integer array of size n, find all elements that appear more than ? n/3 ? times. The algorithm should run in linear time and in O(1) space.

思路依然同 Majority Element 一樣，不同的是我們需要兩個 Majority Element 的候選者，同時需要兩個 count 分別對候選者進行計數(shù)。

count 為 candidate 當前出現(xiàn)的次數(shù)。count == 0 說明當前 candidate 對應的候選者已經被移除，我們需要設定一個新的候選者。

public class Solution {
    public List majorityElement(int[] nums) {
        //問題二：這里給 candidate0 candidate1 初始化值為 0，這會不會影響我們運行的結果？
        int candidate0 = 0,candidate1 = 0,count0 = 0, count1 = 0;
        for(int i = 0; i < nums.length; i++){
            if(candidate0 == nums[i]){
                //當前數(shù)字等于一號候選數(shù)字
                count0++;
            }else if(candidate1 == nums[i]){
                //當前數(shù)字等于二號候選數(shù)字
                count1++;
            }else if(count0 == 0){
                //當前數(shù)字不等于一號候選數(shù)字或二號候選數(shù)字
                //同時必須滿足 count 等于 0，因為如果 count != 0，說明還有候選數(shù)字在等待與它一組的另外兩個數(shù)字
                count0++;
                candidate0 = nums[i];
            }else if(count1 == 0){
                count1++;
                candidate1 = nums[i];
            }else{
                //只有 不滿足以上所有條件我們才能對 count 進行減操作
                count0--;
                count1--;
            }
        }
        
        //**問題三：這里能夠省略 distinct() 嗎？為什么？**
        return Stream.of(candidate0, candidate1).distinct().filter(num -> {
            int count = 0;
            for(int i = 0; i < nums.length; i++){
                if(nums[i] == num){
                    count++;
                }
            }
            return count > nums.length / 3;
        }).collect(Collectors.toList());
    }
}

我們再梳理一遍思路：我們需要找到三個不同的數(shù)字，然后拋棄掉這三個數(shù)字：
首先要判斷是否等于candidate，如果等于candidate那么對應的 candidate 必須加一等待其他的數(shù)字來消除它
當有一個 candidate 的 count 為 0 時，說明該 candidate 已經全部被消除，我們需要設定新的 candidate 數(shù)字。
當一個數(shù)字不等于兩個 candidate，同時兩個 candidate 的 count 都不為零。這意味著當前這個數(shù)字就是這兩個 candidate 等待的第三個數(shù)字。于是這三個數(shù)字被移除，同時他們的 count 都要減一。

這個算法到這里就結束了，時間復雜度是線性的 O(n),空間復雜度是 O(1)。
接下來是問題解答時間：

問題一： if 的判定順序有要求嗎？如果有要求的話應該是怎么樣的呢？

答案是有要求，細心的讀者可能發(fā)現(xiàn)，在 Majority Element 中，我們對 count == 0 的判斷在對 candidate == nums[i] 的判斷之前，而在 Majority Element II 中則正好相反。

這是因為，count == 0 是用來判斷對應 candidate 的當前存活量，在判斷這一步之前，我們必須確保數(shù)組中當前數(shù)字不等于 兩個 candidate中的任意一個。否則，我們可能會在 count0!=0 && count1==0 && nums[i]==candidate0 時錯誤的將 nums[i] 賦值給 candidate1。

問題二：這里給 candidate0 candidate1 初始化值為 0，這會不會影響我們運行的結果？

不會，因為 candidate0 只會在第一次循環(huán)中使用，如果 candidate0 == nums[0]，count++不會引起任何問題。如果 candidate != nums[0] 那么我們此時 count==0 重新初始化 candidate0 == nums[0]，同樣不會有任何影響。

問題二擴充：如果我們初始化 int candidate0 = 0, candidate1 = 1 會不會影響我們的運行結果呢？

問題三：這里能夠省略 distinct() 嗎？為什么？

不能，盡管我們在循環(huán)中首先通過 if(candidate0 == nums[i]) 和 else if(candidate1 == nums[i]) 兩個 if 判斷，使得 candidate0 != candidate1 在絕大部分下成立，但是在一種極為特殊的情況下仍然可能會使得我們得到重復的數(shù)組。

試想當整個數(shù)組所有的數(shù)字都相等的時候，我們 candidate0 和 candidate1 這兩個候選數(shù)字中，有一個數(shù)字將永遠不會被重新賦值,也就是說，有一個數(shù)字將我們賦給的初值保持到了最后。

在我們的代碼中，因為我們將兩個候選數(shù)字都初始化 0，所以當數(shù)組 全為0 時會返回錯誤的結果。

這一點，我們可以通過將兩個候選數(shù)字初始化為不同的數(shù)字來解決：int candidate0 = 0,candidate1 = 1，這樣我們就可以移除掉 distinct() 了