> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/array/169.-majority-element.md).

# 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="/pages/-LbThQW-N2717Cch2ra2" %}
[229. Majority Element II](/practice-of-algorithm-problems/array/229.-majority-element-ii.md)
{% endcontent-ref %}