# 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
# Solution
Approach 1: Hash table.
Approach 2: Sorting.
Approach 3: Boyer-Moore Voting Algorithm.
# Code (Python)
Approach 1:
Approach 2:
Approach 3:
# Code (C++)
Approach 1:
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int,int> numsCount;
for (int i = 0; i < nums.size(); ++i)
{
numsCount[nums[i]]++;
}
int majority = nums.size() / 2;
for (auto iter = numsCount.begin(); iter != numsCount.end(); ++iter)
{
if (iter->second > majority)
return iter->first;
}
return 0;
}
};
Approach 2:
class Solution {
public:
int majorityElement(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
return nums[nums.size()/2];
}
};
Approach 3:
class Solution {
public:
int majorityElement(vector<int>& nums) {
int count = 0;
int majority = NULL;
for (int i = 0; i < nums.size(); ++i)
{
if (count == 0)
majority = nums[i];
if (nums[i] == majority)
count++;
else
count--;
}
return majority;
}
};