求衆數[Leetcode]

求衆數有很多種解法，直覺上第一種就是用哈希表統計，這種方法需要O(n)的時間和空間。另一種叫摩爾投票法，需要O(n)的時間和O(1)的空間，比哈希表要好，這種投票法先将第一個數字假設為衆數，然後把計數器設為1，比較下一個數和此數是否相等，若相等則計數器加1，否則計數器減1.然後看此時計數器的值，若為0，則将下一個值設為候選衆數。以此類推直到周遊完整個數組，目前候選衆數即為該數組的衆數。精妙！通俗的講，他是把原數組精簡化，互相抵消。首先是有個強大的前提存在，就是衆數一定存在。如果計數器減到0了，說明目前不是候選者的數字的個數已經跟候選者出現的個數相同了，那麼這個候選者已經很weak，不一定能出現超過半數，我們選擇更換目前的候選者。那麼可能你會有疑問，那萬一後面又大量出現了之前的候選者怎麼辦，不需要擔心，如果之前的候選者在後面大量出現的話，其又會重新變為候選者，直到最終驗證成為正确的衆數，佩服算法的提出者啊，代碼如下：

class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 1;
        int res = nums[0];
        for(int i=1;i<nums.length;i++){ 
        //也可直接周遊數組for(int num:nums)
            if(cnt == 0){
                res = nums[i];
            }
            else if(res == nums[i]) ++cnt;
            else --cnt;             
        }
        return res;
    }
}          

還有一種解法用到了位操作，将衆按位來建立，從0到31位，每次統計下數組中該位上0和1的個數，如果1多，那麼我們将結果res中該位變為1，最後累加出來的res就是衆數了，相當贊的方法，這種思路尤其在這道題的延伸Majority Element II中有重要的應用，參見代碼如下：

public class Solution {
    public int majorityElement(int[] nums) {
        int res = 0, n = nums.length;
        for (int i = 0; i < 32; ++i) {
            int ones = 0, zeros = 0;
            for (int num : nums) {
                if (ones > n / 2 || zeros > n / 2) break;
                if ((num & (1 << i)) != 0) ++ones;
                else ++zeros;
            }
            if (ones > zeros) res |= (1 << i);
        }
        return res;
    }
}      

或許這就是帶佬的操作8。