###### tags: `Leetcode` `easy` `hash` `python` `c++` `Top 100 Liked Questions`

# 169. Majority Element

## [題目連結:] https://leetcode.com/problems/majority-element/

## 題目:
Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

**Follow-up: Could you solve the problem in linear time and in O(1) space?**


#### [圖片來源:] https://leetcode.com/problems/majority-element/

## 解題思路:
* 要求linear time and in O(1) space
技巧: 使用**摩爾投票Moore voting algorithm** :
* Time: O(n)
* Spane: O(1)
* **step1**: 因為題目定最大數一定超過一半，使用count紀錄當前位置數字x出現的次數
* **step2**: 依序遍歷數組 當與x相同 counter+=1 else counter-=1
* **step3**: 若counter=-1 x換為當前的val
## Python:

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res=nums[0]
        count=1
        for pos in range(1,len(nums)):
            if nums[pos]==res:
                count+=1
            else:
                count-=1
                if count<0:
                    res=nums[pos]
                    count=1
        return res
        
if __name__ == '__main__':
    result = Solution()
    nums = [2,2,1,1,1,2,2]
    ans = result.majorityElement(nums)
    print(ans)

## C++:

#include<iostream>
#include<vector>
using namespace std;

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

int main(){
    vector<int> nums={2,2,1,1,1,2,2};
    Solution res;
    cout<<res.majorityElement(nums)<<endl;
    return 0;
}