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
// 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;
}
// 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;
}
// 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;
}