hello all
I'm trying to write a program that returns us majority element.
An array is said to have a majority element if more than half of its entries are the same - >(size of the array)/2.
It wouldn't be a problem if i had no conditions, but i have to write it in O(n log n) time complexity - so basically this means that i have to use recursive approach / quicksort algorithm.
I've found this code and tried to make it work but i just can't do it...
So, I'd be very grateful if someone could help me out (it seems that there's a problem in my recursion settings).
THANKS a lot!
p.s.: - please note that solution should be in O(n log n) time complexity.
- i have a basic knowledge about c++, so please forgive me if some of the errors in the code look "stupid".
#include <iostream>
using namespace std;
int majority(int *A, int inL, int inD)
{
if(inD == 1)
return A[0];
int majorL = majority(A, inL, inD/2-1);
int majorD = majority(A, inD/2+1, inD);
int count = 0;
for(int i=0; i<inD; i++)
if(A[i] == majorL)
count++;
if(count > inD/2)
return majorL;
count = 0;
for(int i=0; i<inD; i++)
if(A[i] == majorD)
count++;
if(count > inD/2)
return majorD;
}
return -1;
}
int main()
{
int array[10] = {2,3,2,2,4,2,2,2,4,4};
int indexL = 0;
int indexD = 9; //CHANGE IT IF YOU CHANGE ARRAY SIZE (indexD = ARRAY_SIZE - 1)!!!
for(int i=0; i<10; i++)
cout << array[i] << " ";
int x = majority(array, indexL, indexD);
if(x == -1)
cout << "\n\nNo majority element!\n";
else
cout << "\n\nMajority element is: " << x << "\n";
return 0;
}