The majority element is the element that occurs more than half of the size of the array.
Algorithm below loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1. First Phase algorithm gives us a candidate element. In second phase we need to check if the candidate is really a majority element.
Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2.
Moore’s Majority Algorithm:
c = particular candidate
Step 0: Initialize count to be zero
Step 1: Go through the vote
i. Check if the count is zero
if so then assign the c to this vote’s candidate and then set count=1
if not then check if this vote’s candidate is equal to c
if yes then set count+=1
if no then set count-=1
Step 2: Continue until the end
Step 3: For that c,Check once again by going through the votes if it is really the majority.
Function provided below returns -1 if there is no majority element otherwise that element.
int findMajorityElement(int * arr, int size)
{
int count = 0, i, majorityElement;
for (i = 0 ; i < size ; i++)
{
if (count == 0) {
majorityElement = arr[i];
count = 1;
}
else
{
if(arr[i] == majorityElement)
count++;
else
count--;
}
}
count = 0;
for (i = 0; i < size; i++) {
if (arr[i] == majorityElement) {
count++;
}
if (count > size/2) {
return majorityElement;
}
else return -1;
}
Time Complexity : O(n)
Space Complexity : O(1)
want some more explanation plz..
@naveen
Majority element is that occurs more than half the size of the array. For this moore suggested this algo, in which loop through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1. By doing this u are ensuring this that u are getting element which gets max vote that means only possibility that an element in array exist that has majority only if this occurs more than half the size of array.
Take different cases and pick pen and paper , u will be more clear.
Does the algorithm really find majority element or it just checks if an element can be majority element or not ? Since when count = 0, majorityElement is initialized and throughout the other iterations of the loop, the algorithm just increments or decrements the count value depending on the number of the occurrences of the element as well as other elements also. So to find out the majority element the function should be called again and again on all the elements of the array untill we find the majority element.
I guess it will give wrong answer in case of 1,2,3,3,2,2 as it is considering maximum recurring element as 3 not 2 which is wrong .
I guess it can be corrected if you write the count==0 condition after the incrementing count position . Below are the codes in python which show the problem in the method suggested by you .
lst=[1,2,3,3,2,2]
currentCount = 0
currentValue = lst[0]
for val in lst:
if currentCount == 0:
currentValue = val
currentCount = 1
if val == currentValue:
currentCount += 1
else:
currentCount -= 1
print currentCount,currentValue
print(currentValue)
This code gives answer as
2 1
1 1
0 1
2 3
1 3
0 3
3
while this code
lst=[1,2,3,3,2,2]
currentCount = 0
currentValue = lst[0]
for val in lst:
if val == currentValue:
currentCount += 1
else:
currentCount -= 1
if currentCount == 0:
currentValue = val
currentCount = 1
print currentCount,currentValue
print(currentValue)
gives answer as
1 1
1 2
1 3
2 3
1 3
1 2
2
which is correct .
Hi Tushar,
There is no majority element in this array [1,2,3,3,2,2]. According to definition,majority element is the element that occurs more than half of the size of the array. Provided code will return -1 which is correct.
The code is working correctly though but the essence is wrong … as in First the code should find the maximum recurring element in the array and then count the number of time it is occuring . And your code is finding the maximum recurring element as wrong .
In case if the question defines majority element as the element which occurs >= half the size of array ? Then your code will give wrong answer as 3 but the answer is 2 in that case …