# Boyer–Moore 多數投票
- [Leetcode 169. Majority Element](https://leetcode.com/problems/majority-element/)
- [Leetcode 229. Majority Element II](https://leetcode.com/problems/majority-element-ii/)
- 給定一個大小為 n 的 array，其中有一數字出現超過一半，請找出此數字為何?

    int majorityElement(vector<int>& nums) {
        int cnt = 0, cand = -1;
        for(auto d:nums){
            if(cnt==0)  cand = d;
            if(cand==d) cnt++;
            else        cnt--;
        }
        return cand;
    }

- 概念，兩兩消除，最後多的那些元素就會是答案
- 給定一個大小為 n 的 array，其中有些數字出現 1/3，請找出那些數字

    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        int cnt1 = 0, ans1 = -1, cnt2 = 0, ans2 = -1;
        
        for(auto d:nums){
            if(d==ans1)         cnt1++;
            else if(d==ans2)    cnt2++;
            else if(cnt1==0)    {cnt1 = 1; ans1 = d;}
            else if(cnt2==0)    {cnt2 = 1; ans2 = d;}
            else                {cnt1--;   cnt2--;}
        }
        
        cnt1 = cnt2 = 0;
        for(auto d:nums){
            if(d==ans1) cnt1++;
            else if(d==ans2) cnt2++;
        }
        vector<int> ans;
        if(3*cnt1>n)   ans.push_back(ans1);
        if(3*cnt2>n)   ans.push_back(ans2);
        return ans;
    }