Make delicious recipes!

Find majority element in an unsorted array

If the array were sorted, then majority element could be found by a modified binary search in log N time

If its unsorted, then since the majority element occurs n/2+1 times, we can see that its count can not decrease to 0 if we increment count on its occurrence and decrement count on its absence.

So the following code can help us find the majority element:




Note: After finding the probable candidate, another pass is required to ensure that the candidate is indeed majority.
Without this pass, the algo can fail for cases like the following:


Case 1:   5, 6, 6, 7, 8, 9
Case 2:   5, 9, 2, 3

Note 2: The algorithm works only for true majority elements (i.e. whose frequency is greater than or equal to n/2+1 i.e. more than half).
It fails even for cases where frequency is exactly half.
For example, it fails in the following:
4,4,4,3,5,6






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal