【算法】摩爾投票

【摩爾投票】

　　問題： （majority element）若有一個數組L，長度為n，找出是否有一個數N，N的出現次數大于等于n/2。

　　問題不算太難，一般可以通過周遊計數，或者排序找中位數的辦法來解決。但是如果要求時間複雜度是O(n)，空間複雜度是O(1)，那麼恐怕就沒那麼簡單了。摩爾投票算法正好是這麼一個O(n)和O(1)的算法。

　　

　　●  描述

　　聲明m=0和cnt=0兩個變量後面用。

　　周遊數組，當cnt為0時将目前周遊到的元素指派給m，然後cnt+=1。若cnt不為0，且周遊到的元素等于目前的m，那麼cnt += 1,；若cnt不為0，但是周遊到的元素也不等于目前的m，那麼cnt -= 1。最終周遊完成之後，變量m的值就是我們要找的那個majority element。

　　為什麼這個算法奏效？我們姑且從感性的角度來了解一下。既然是投票，那麼就把這個數組YY成一個投票人的集合。這些投票人心中都有自己想要投的人，然後我們要找出的就是哪個候選人得票能過半的。因為我們無法做到同時聽取所有人的想法，是以我們采取一種“淘汰制”選擇。首先第一個人上台說明他想要推舉的候選人比如說a。如果第二個人也是推舉a的，那麼可以認為a的人氣是兩人份的。第三人如果不是推舉a的，那麼他将減少a的一份人氣。因為選舉是要求最終得票過半，是以對于候選人a來說，每一個人不投票給他，就相當于他損失了一票。若第四人也不投a，則a的人氣歸零，和其他候選人重回起跑線，但此時站在候選台上的仍然是a。此時第五人若想就可以推舉他想選的人b，把a給擠下來，b的人氣為1。以此類推… 從大局上講，如果a的支援者勢力足夠強大，那麼無論a被打倒多少次，最終還是能夠回到候選台上。這邊勢力強大的具體量化就是a的支援者至少達到n/2人。這樣即使前一半人都支援a，後一半人都不支援a，最終a的人氣歸零，但是還是保證站在候選台上的是a。

　　上面就是對投票算法的一個粗淺且感性的了解。

　　●  代碼：

def vote(a):
    m,cnt = 0,0
    for n in a:
        if cnt == 0:
            m = n
            cnt = 1
        elif n == m:
            cnt += 1
        else:
            cnt -= 1
    return m      

　　上述過程中并沒有對投票者支援的人非常分散的情況作出判斷。即無法完成選舉的時候不會給出無法完成的錯誤，而是傳回了接近數組末尾的某個“勢力相對較強”的元素。如果需要對是否超過n/2做判斷那麼可以再去周遊依次數組，看到底m元素出現了幾次，是否達到标準即可。

　　●  更複雜一點

　　如果将問題換成，找出所有出現次數大于n/3次的元素呢。顯然，這種元素最多隻能有兩個。是以我們可以使用投票算法，将有可能是符合要求的兩個元素找出來，然後再看他們是否都超過了n/3來判斷是否選擇它們作為需要選出來的元素。

　　具象到選舉中來，那麼可以認為現在要選的人是兩個。而且這兩個人競選的位置是平級，不分先後的，是以熱門候選人a和熱門候選人b的支援者之間不構成直接競争。是以，算法就變成了，第一人推薦a，a走上甲候選台。第二人推薦b，b走上乙候選台，而此時對a不構成影響是以a的人氣不減。如果第三人推薦的是c，那麼a和b的人氣都要減一份，都歸零了（顯然不能隻減一個人的人氣，否則另一個人就可能會出現明明支援者很少，但是由于推舉的順序比較靠前是以當選的bug）。如果此時第四人支援的不是a或者b而是d，那麼就可以從甲乙任意一個候選台中擠走一個。比如擠走a，之後d的人氣是1，而另一個候選台上的b仍然是0人氣。這麼循環下去，由于a和b不互相競争，是以通過這個算法得到的a和b是所有候選人中相對強勢的兩個。

　　代碼的實作也不複雜：

def vote(a):
    m,n = 0,0
    cm,cn = 0,0
    for i in a:
        if cm == 0: m = i; cm += 1
        elif cn == 0: n = i; cn += 1
        elif i == m: cm += 1
        elif i == n: cn += 1
        else: cm -= 1; cn -= 1
    return m,n      

　　* 其實摩爾投票，主要是為了能夠在O(n)的時間和O(1)的空間解決問題。如果沒有這些限制，那麼使用HashMap或者其他的一些什麼方法則要比這種方法好了解得多多。