---
# System prepended metadata

title: "(Easy) 169.\tMajority Element"
tags: [leetcode]

---

# (Easy) 169.	Majority Element
## Run Code
![](https://i.imgur.com/ExhtMLF.png)

## 題意
在名為nums的arrray中，找出當中出現最多次的那一個。
## 解題思路
就找出最多的那一個OWO
## 困難之處
沒甚麼困難的，差別只有Big O 的問題。
(p.s)下面還有提供一個O(n)的code。
## Code
```cpp=
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        std::map<int,int> number;
        for(std::vector<int>::iterator it=nums.begin();it!=nums.end();it++)
            number[*it]++;
        std::map<int,int>::iterator answer=number.begin();
        for(std::map<int,int>::iterator it=number.begin();it!=number.end();it++)
            if(it->second > answer->second)
                answer = it;
        return answer->first;
    }
};
```
## Code with O(n)
```cpp=
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major=nums[0], count=1;
        for(int i=1;i<nums.size();i++){
            if(count==0){
                count++;
                major = nums[i];
            }
            else if(major==nums[i])
                count++;
            else
                count--;
        }
        return major;
    }
};
```
###### tags: `leetcode`