Finding Majority Element in Array.

Find Majority Element in Array.

 

For a given input array we need to find the majority element.
An element is said to be majority element if its frequency of occurrence exceeds n/2.
Input : 3 3 4 2 4 4 2 4 4
Output: 4

Input : 3 3 4 2 4 4 2 4
Output: NONE

Solution 1: A basic solution is to scan entire array for checking for every element in the array. If any element occurs more than n/2 time, prints it and break the loop. This will be of O(n^2) complexity.

Solution 2: Sort the entire array in O(nlogn) and then in one pass keep counting the elements. This will be of O(nlogn) + O(n) = O(nlogn) complexity.

If we are sure that there is a majority element for sure that we can do it in constant time in the sorted array. I am leaving an exercise to readers that how can we do that in constant time.

Solution 3 Hash map-based approach.
We construct a hash map of the elements and store the frequency of their occurrence.

Code:-

[code language=”cpp”]

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
//code
int n,t,i,a;
cin>>t;
while(t–)
{bool flag =false;
cin>>n;
unordered_map<int,int> s; // a map which stores element as key and also its frequency.
for(i=0;i<n;i++)
{
cin>>a;

s[a]++;

}
auto it = s.begin();//iterator to traverse the map.
for(;it!=s.end();++it){
if(it->second>n/2){// comparing the value of frequency.
cout<<it->first;
flag = true;
break;
}
}

if(!flag)
cout<<"NO Majority Element";
cout<<endl;

}
return 0;
}
[/code]

Time complexity for this O(n)
However the space complexity also gets involved in this which is also O(n).

In order to reduce the space complexity refer Moore’s Voting Algorithm.https://prepinsta.com/boyer-moore-majority-vote-algorithm/

Please Login/Signup to comment