# 169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears **more than** `⌊ n/2 ⌋` times.

You may assume that the array is non-empty and the majority element always exist in the array.

**Example 1:**

```
Input: [3,2,3]
Output: 3
```

**Example 2:**

```
Input: [2,2,1,1,1,2,2]
Output: 2
```

```cpp
// Hashtable 
int majorityElement(vector<int>& nums) { // time: O(n); space: O(n)
    int n = nums.size();
    unordered_map<int, int> mp;
    for (int num : nums) {
        if (++mp[num] > n / 2) return num;
    }
    return -1;
}
```

```cpp
// Moore Voting Method
int majorityElement(vector<int>& nums) { // time: O(n); space: O(1)
    int res = 0, cnt = 0;
    for (int num : nums) {
        if (cnt == 0) {
            res = num;
            ++cnt;
        } else {
            (num == res) ? ++cnt : --cnt;
        }
    }
    return res;
}
```

```cpp
// Bit Manipulation
int majorityElement(vector<int>& nums) { // time: O(n); space: O(1)
    int res = 0, n = nums.size();
    long mask = 1;
    for (int i = 0; i < 32; ++i, mask <<= 1) {
        int bitCount = 0;
        for (int num : nums) {
            if (num & mask) ++bitCount;
            if (bitCount > n / 2) {
                res |= mask;
                break;
            }
        }
    }
    return res;
}
```

{% content-ref url="229.-majority-element-ii" %}
[229.-majority-element-ii](229.-majority-element-ii)
{% endcontent-ref %}
