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
|
