【LeetCode169】多數元素（摩爾投票法）

文章目錄

• ​​1.題目​​
• ​​2.法一：用sort​​
• ​​3.法二：摩爾投票法（Boyer-Moore）​​

1.題目

2.法一：用sort

先用sort排序後，因為定義的“多數元素”是在數組中出現次數大于n/2的元素，是以可以傳回下标為n/2的數組元素即所求。

用sort的時間複雜度就是O(nlogn)而非O(n)了。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};      

3.法二：摩爾投票法（Boyer-Moore）

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate=nums[0];
        int count=1;
        for(int i=1;i<nums.size();i++){
            if(candidate==nums[i]){
                count++;//遇到相同的則票數+1
            }else{
                //遇到不同
                if(--count==0){//票數為0則替換候選人
                    candidate=nums[i];
                    count=1;//重置1
                }
            }
        }
        return candidate;
    }
};