Majority Element
17.10 Majority Element: A majority element is an element that makes up more than half of the items in an array. Given a positive integers array, find the majority element. If there is no majority element, return -1. Do this in 0 (N) time and O( 1) space.
EXAMPLE
Input: 1 2 5 9 5 9 5 5 5
Output: 5
Complexity: O(n) time and O(1) space
The Idea: The majority element of an array is guareenteed to be iterated over
floor(n/2) times. Less frequent elements are then filtered out because contrasting elements cancel each other out.int majorityElement(vector<int>& nums) {
if (nums.empty()) return -1;
int maj = nums[0];
int count = 1;
for (int i = 1; i < nums.size(); i++) {
if (!count) {
maj = nums[i];
count++;
}
else if (nums[i] == maj) count++;
else count--;
}
return maj;
}
int main()
{
vector<int> t1 = { 1, 2, 5, 9, 5, 9, 5, 5, 5 };
cout << majority_element(t1);
}
Last modified 3yr ago