# 169-Majority Element
###### tags: `Easy`
## Question
https://leetcode.com/problems/majority-element/
## Key
## Reference
## Solution
### Hash table solution

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> umap;
        int n = nums.size();

        for(int i = 0; i < n; i++)
        {
            umap[nums[i]]++;  
            if(umap[nums[i]] > n/2)
            {
                return nums[i];
            }
        }
        return 0;    
    }
};

### solution with less space
但這個方法只能用在一個array，只出現兩種數字的情況

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