How to find the majority element in an array
Educative Answers TeamThe majority element is an element in an array that occurs more than (size/2) times in an array (where size is the number of elements stored in an array).
The algorithms
There are two ways to find the majority element in an array:
Basic method
This method has two loops that count the maximum occurrence of each element in an array. Whenever the maximum count becomes greater than the size/2, the loops break and display the element as the majority element of an array. The time complexity of this method in terms of BigO is .
Using HashMap
The basic method is computationally expensive as it has a BigO of . To reduce the BigO, a HashMap can be used to find the majority element in . HashMap will store the count of occurrences of an element and the element itself.
Implementation
The code below uses the basic method to find the majority element of an array:
#include <iostream>
using namespace std;
//function to find the majority element
void findMajority(int arr[], int size)
{
int maxCount = 0;
int index = -1; // sentinels
for(int i = 0; i < size; i++)
{
int count = 0;
for(int j = 0; j < size; j++)
{
if(arr[i] == arr[j])
count++;
}
// update maxCount if the count of the current element is greater
if(count > maxCount)
{
maxCount = count;
index = i;
}
}
// if the maxCount is greater than size/2,
// return the corresponding element.
if (maxCount > size/2)
cout << "Majority element is " <<arr[index] << endl;
else
cout << "Majority Element does not exist" << endl;
}
// Driver code
int main()
{
int arr[] = {1,3,4,4,1,4,4};
int size = sizeof(arr) / sizeof(arr[0]);
// Calling the function
findMajority(arr, size);
return 0;
} Implementation
The code below uses a HashMap to find the majority element of an array:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void findmajority(int arr[], int size)
{
unordered_map<int, int> myHashMap;
for(int i = 0; i < size; i++)
myHashMap[arr[i]]++;
int count = 0;
for(auto i : myHashMap)
{
if(i.second > size / 2)
{
count =1;
cout << "Majority elemet is " << i.first<<endl;
break;
}
}
if(count == 0)
cout << "Majority element does not exist" << endl;
}
// Driver code
int main()
{
int arr[] = {1,3,4,4,1,4,4};
int n = sizeof(arr) / sizeof(arr[0]);
// Calling the function.
findmajority(arr, n);
return 0;
} RELATED TAGS
View all Courses
