###### tags: `LeetCode` `Medium`
# LeetCode #229 [Majority Element II](https://leetcode.com/problems/majority-element-ii)
### (Medium)
給定一個大小為 n 的整數數組，找出其中所有出現超過 ⌊ n/3 ⌋ 次的元素。
進階：嘗試設計時間複雜度為 O(n)、空間複雜度為 O(1)的算法解決此問題。

---
使用Boyer–Moore majority vote algorithm, nums[i]與候選數相同則計數器+1, 不同則-1, 若計數器為0則替換候選數。
遍歷nums後得到兩候選數, 在計算這兩個候選數個數是否大於n/3。

---

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        if(nums.size()==1)return {nums[0];};
        else{
            int element1=0;
            int count1=0;
            int element2=0;
            int count2=0;
            for(int i=1;i<nums.size();i++){
                if(element1==nums[i])count1++;
                else if(element2==nums[i])count2++;
                else if(count2==0){
                    element2=nums[i];
                    count2=1;
                }
                else if(count1==0){
                    element1=nums[i];
                    count1=1;
                }
                else{
                    count1--;
                    count2--;
                }
            }
            count1=0;count2=0;
            for(int i=0;i<nums.size();i++){
                if(nums[i]==element1)count1++;
                else if (nums[i]==element2)count2++;
            }
            vector<int> ans;
            if(count1>(nums.size()/3))ans.push_back(element1);
            if(count2>(nums.size()/3))ans.push_back(element2);
            return ans;
        }
    }
};