169. Majority Element

解法

使用多數投票算法來解決此問題。

多數投票算法:

• 前提: 數列中必定有一數值過半數
• 做法:
  • 從第一個數值開始， 設 vote = 1, ans = nums[0]
  • 若下個數字與 ans 相同則 vote++
  • 如不同則 vote--
  • 當 vote == 0 則修改 ans, vote
• 想法: 因為必定有一值大於 n/2，所以在這一增一減情況下，最後一定會留下 n/2 的值

程式碼

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int vote = 1;
        int ans = nums[0];
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] != ans){
                vote--;
                if(vote == 0){
                    vote = 1;
                    ans = nums[i];
                }
            }else{
                vote++;
            }
        }
        return ans;
    }
};