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
Link: https://leetcode.com/problems/majority-element/
Solution using unordered_map in C++:
#
class Solution {
public:
int majorityElement(vector
for(int i=0;i<n;i++) {
mp\[a\[i\]\]++;
}
for(int i=0;i<n;i++) {
if(mp\[a\[i\]\] > (n/2)) {
n = a\[i\];
break;
}
}
return n;
}
};
It has \(O(n)\) time complexity and \(O(n)\) space complexity.
Solution using the Boyer-Moore voting algorithm in C++ #
class Solution {
public:
int majorityElement(vector
n = a.size();
// finding the candidate
candidate = a\[0\];
count = 1;
for(int i=1;i<n;i++) {
if(candidate != a\[i\]) {
count--;
}else{
count++;
}
if(count == 0) {
candidate = a\[i\];
count = 1;
}
}
// find the majority candidate
count = 0;
for(int i=0;i<n;i++) {
if(a\[i\] == candidate) {
count++;
}
if(count > (n/2)) {
break;
}
}
return candidate;
}
};
Time complexity is same as the previous solution but we improved the space complexity to \(O(1)\).
The algorithm is well explained here