Menu
Can anyone think of a linear time algorithm for determining a majority element in a list of elements? The algorithm should use O(1) space.
If n is the size of the list, a majority element is an element that occurs at least ceil(n / 2) times.
[Input] 1, 2, 1, 1, 3, 2
[Output] 1
[Editor Note] This question has a technical mistake. I preferred to leave it so as not to spoil the wording of the accepted answer, which corrects the mistake and discusses why. Please check the accepted answer.
325
This algorithm works on the fact that if an element occurs more than N/2 times, it means that the remaining elements other than this would definitely be less than N/2.
Time complexity = 32 * O(n) * O(1) = O(n).
For example, if a group consists of 20 individuals, a majority would be 11 or more individuals, while having 10 or fewer individuals would not constitute a majority. "Majority" can be used to specify the voting requirement, as in a "majority vote", which means more than half of the votes cast.
I would guess that the Boyer-Moore algorithm (as linked to by nunes and described by cldy in other answers) is the intended answer to the question; but the definition of "majority element" in the question is too weak to guarantee that the algorithm will work.
If n is the size of the list. A majority element is an element that occurs at least ceil(n/2) times.
The Boyer-Moore algorithm finds an element with a strict majority, if such an element exists. (If you don't know in advance that you do have such an element, you have to make a second pass through the list to check the result.)
For a strict majority, you need "... strictly more than floor(n/2) times", not "... at least ceil(n/2) times".
In your example, "1" occurs 3 times, and other values occur 3 times:
Example input: 1, 2, 1, 1, 3, 2
Output: 1
but you need 4 elements with the same value for a strict majority.
It does happen to work in this particular case:
Input: 1, 2, 1, 1, 3, 2 Read 1: count == 0, so set candidate to 1, and set count to 1 Read 2: count != 0, element != candidate (1), so decrement count to 0 Read 1: count == 0, so set candidate to 1, and set count to 1 Read 1: count != 0, element == candidate (1), so increment count to 2 Read 3: count != 0, element != candidate (1), so decrement count to 1 Read 2: count != 0, element != candidate (1), so decrement count to 0 Result is current candidate: 1
but look what happens if the final "1" and the "2" at the end are swapped over:
Input: 1, 2, 1, 2, 3, 1 Read 1: count == 0, so set candidate to 1, and set count to 1 Read 2: count != 0, element != candidate (1), so decrement count to 0 Read 1: count == 0, so set candidate to 1, and set count to 1 Read 2: count != 0, element != candidate (1), so decrement count to 0 Read 3: count == 0, so set candidate to 3, and set count to 1 Read 1: count != 0, element != candidate (3), so decrement count to 0 Result is current candidate: 3
82
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
