投票算法

摩爾投票算法（求衆數）

問題

來自leetcode算法題，求衆數

給定一個大小為 n 的數組，找到其中的衆數。衆數是指在數組中出現次數大于 ⌊ n/2 ⌋ 的元素。

你可以假設數組是非空的，并且給定的數組總是存在衆數。

示例

示例 1:

輸入: [3,2,3]

輸出: 3

示例 2:

輸入: [2,2,1,1,1,2,2]

輸出: 2

解決這個問題，除了暴力比對、哈希表（線性的時間複雜度）、分治之外，我覺得最适合的就是摩爾投票算法。

算法思想

在每一輪投票過程中，從數組中找出一對不同的元素，将其從數組中删除。這樣不斷的删除直到無法再進行投票，如果數組為空，則沒有任何元素出現的次數超過該數組長度的一半。如果隻存在一種元素，那麼這個元素則可能為目标元素。

詳解

來自官方

想法

如果我們把衆數記為 +1+1 ，把其他數記為 -1−1 ，将它們全部加起來，顯然和大于 0 ，從結果本身我們可以看出衆數比其他數多。

算法

本質上， Boyer-Moore 算法就是找 nums 的一個字尾 sufsuf ，其中 suf[0]suf[0] 就是字尾中的衆數。我們維護一個計數器，如果遇到一個我們目前的候選衆數，就将計數器加一，否則減一。隻要計數器等于 0 ，我們就将 nums 中之前通路的數字全部 忘記 ，并把下一個數字當做候選的衆數。直覺上這個算法不是特别明顯為何是對的，我們先看下面這個例子（豎線用來劃分每次計數器歸零的情況）

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

首先，下标為 0 的 7 被當做衆數的第一個候選。在下标為 5 處，計數器會變回0 。是以下标為 6 的 5 是下一個衆數的候選者。由于這個例子中 7 是真正的衆數，是以通過忽略掉前面的數字，我們忽略掉了同樣多數目的衆數和非衆數。是以， 7 仍然是剩下數字中的衆數。

代碼

class Solution {
    public int majorityElement(int[] nums) {
        // 初始票數記為0
        int votes = 0;
        int target = 0;

        for (int i : nums) {
            if (votes == 0) {
                target = i;
            }
            votes += target == i ? 1 : -1;
        }
        
        return target;
    }
}