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

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

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

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

我們可以遍歷數(shù)組,當(dāng)碰到兩個(gè)不一樣的數(shù)字時(shí),我們將這兩個(gè)數(shù)字同時(shí)丟棄這兩個(gè)數(shù)字中可能有一個(gè)為 Majority Element,也可能兩個(gè)都不為Majority Element.因?yàn)?b>k 大于 n/2,所以在最差情況下(每次移除不同數(shù)字時(shí)都包含一個(gè)Majority Element),我們?nèi)匀荒軌虮ＷC最后得到的數(shù)字是Majority Element.

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

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

很容易算出最后剩余的Majority Element個(gè)數(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 的判定順序有要求嗎？如果有要求的話應(yīng)該是怎么樣的呢？
            if(count == 0){
                count++;
                candidate = nums[i];
            }else if(candidate != nums[i]){
                count--;
            }else{
                count++;
            }
        }
        return candidate;
    }
}

這個(gè)算法很經(jīng)典，也很簡(jiǎn)單，畢竟不用自己想。

接下來，我們可以對(duì)這個(gè)算法做一些簡(jiǎn)單的擴(kuò)展，我們當(dāng)前定義的 Majority Element 的數(shù)量大于 n/2 的元素。

如果我們?cè)谕镀敝灰獫M足投票數(shù)量超過 n/3 即認(rèn)為它是最大投票，我們能不能求出這個(gè)值呢？

媽蛋，文章中這種問題就跟小說里主角跳崖會(huì)不會(huì)死一樣，有標(biāo)準(zhǔn)答案的。
喬治啊啊馬?。?？

最大投票資料片：熊貓人之謎 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 一樣，不同的是我們需要兩個(gè) Majority Element 的候選者，同時(shí)需要兩個(gè) count 分別對(duì)候選者進(jìn)行計(jì)數(shù)。

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

public class Solution {
    public List majorityElement(int[] nums) {
        //問題二：這里給 candidate0 candidate1 初始化值為 0，這會(huì)不會(huì)影響我們運(yùn)行的結(jié)果？
        int candidate0 = 0,candidate1 = 0,count0 = 0, count1 = 0;
        for(int i = 0; i < nums.length; i++){
            if(candidate0 == nums[i]){
                //當(dāng)前數(shù)字等于一號(hào)候選數(shù)字
                count0++;
            }else if(candidate1 == nums[i]){
                //當(dāng)前數(shù)字等于二號(hào)候選數(shù)字
                count1++;
            }else if(count0 == 0){
                //當(dāng)前數(shù)字不等于一號(hào)候選數(shù)字或二號(hào)候選數(shù)字
                //同時(shí)必須滿足 count 等于 0，因?yàn)槿绻?count != 0，說明還有候選數(shù)字在等待與它一組的另外兩個(gè)數(shù)字
                count0++;
                candidate0 = nums[i];
            }else if(count1 == 0){
                count1++;
                candidate1 = nums[i];
            }else{
                //只有 不滿足以上所有條件我們才能對(duì) count 進(jìn)行減操作
                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());
    }
}

我們?cè)偈崂硪槐樗悸罚何覀冃枰业饺齻€(gè)不同的數(shù)字，然后拋棄掉這三個(gè)數(shù)字：
首先要判斷是否等于candidate，如果等于candidate那么對(duì)應(yīng)的 candidate 必須加一等待其他的數(shù)字來消除它
當(dāng)有一個(gè) candidate 的 count 為 0 時(shí)，說明該 candidate 已經(jīng)全部被消除，我們需要設(shè)定新的 candidate 數(shù)字。
當(dāng)一個(gè)數(shù)字不等于兩個(gè) candidate，同時(shí)兩個(gè) candidate 的 count 都不為零。這意味著當(dāng)前這個(gè)數(shù)字就是這兩個(gè) candidate 等待的第三個(gè)數(shù)字。于是這三個(gè)數(shù)字被移除，同時(shí)他們的 count 都要減一。

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

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

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

這是因?yàn)椋?b>count == 0 是用來判斷對(duì)應(yīng) candidate 的當(dāng)前存活量，在判斷這一步之前，我們必須確保數(shù)組中當(dāng)前數(shù)字不等于 兩個(gè) candidate中的任意一個(gè)。否則，我們可能會(huì)在 count0!=0 && count1==0 && nums[i]==candidate0 時(shí)錯(cuò)誤的將 nums[i] 賦值給 candidate1。

問題二：這里給 candidate0 candidate1 初始化值為 0，這會(huì)不會(huì)影響我們運(yùn)行的結(jié)果？

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

問題二擴(kuò)充：如果我們初始化 int candidate0 = 0, candidate1 = 1 會(huì)不會(huì)影響我們的運(yùn)行結(jié)果呢？

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

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

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

在我們的代碼中，因?yàn)槲覀儗蓚€(gè)候選數(shù)字都初始化 0，所以當(dāng)數(shù)組 全為0 時(shí)會(huì)返回錯(cuò)誤的結(jié)果。

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