Linear Time Voting Algorithm. I don't get it
Solution 1
The algorithm only works when the set has a majority -- more than half of the elements being the same. AAACCBB
in your example has no such majority. The most frequent letter occurs 3 times, the string length is 7.
Solution 2
Small but an important addition to the other explanations. Moore's Voting algorithm has 2 parts -
first part of running Moore's Voting algorithm only gives you a candidate for the majority element. Notice the word "candidate" here.
In the second part, we need to iterate over the array once again to determine if this candidate occurs maximum number of times (i.e. greater than size/2 times).
First iteration is to find the candidate & second iteration is to check if this element occurs majority of times in the given array.
So time complexity is: O(n) + O(n) ≈ O(n)
Solution 3
From the first linked SO question:
with the property that more than half of the entries in the array are equal to N
From the Boyer and Moore page:
which element of a sequence is in the majority, provided there is such an element
Both of these algorithms explicitly assume that one element occurs at least N/2 times. (Note in particular that "majority" is not the same as "most common.")
Lieven Keersmaekers
Application Developer, infected by TDD. Answers/websites that I frequently refer to: XY Problem Teach yourself programming in 10 years You should accept answers to some of your past questions. Not only will this show your appreciation for the people who spent their own time to help you, but it will improve your accept rate and the chances that they will answer any future questions you may have. Favorite Quotes The subset of problems that have elegant software solutions is significantly smaller than the set of problems that are economically useful to solve. (Scott Leadley) It always amazes me that people expect me to spend my time answering questions they won't spend their time asking. (George) What have you tried.com In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt. Blair P. Houghton. Programmer. If Java had true garbage collection, most programs would delete themselves upon execution. Robert Sewell. Programmer.
Updated on June 14, 2022Comments
-
Lieven Keersmaekers almost 2 years
As I was reading this (Find the most common entry in an array), the Boyer and Moore's Linear Time Voting Algorithm was suggested.
If you follow the link to the site, there is a step by step explanation of how the algorithm works. For the given sequence,
AAACCBBCCCBCC
it presents the right solution.When we move the pointer forward over an element e:
- If the counter is 0, we set the current candidate to e and we set the counter to 1.
- If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.
If I use this algorithm on a piece of paper with
AAACCBB
as input, the suggested candidate would become B what is obviously wrong.As I see it, there are two possibilities
- The authors have never tried their algorithm on anything else than
AAACCBBCCCBCC
, are completely incompetent and should be fired on the spot (doubtfull). - I am clearly missing something, must get banned from Stackoverflow and never be allowed again to touch anything involving logic.
Note: Here is a a C++ implementation of the algorithm from Niek Sanders. I believe he correctly implemented the idea and as such it has the same problem (or doesn't it?).
-
leo7r about 15 yearsHappens to everyone. Do not be too strict in carrying out point 2. from your answer :)
-
Lieven Keersmaekers about 15 years+1. Close second. Can't believe I've overlooked that. Thanks.
-
imreal almost 11 years+1 I was about to write about the completely overlooked fact that a second iteration is necessary to verify the candidate. Hopefully the OP will notice this late answer.
-
texens over 10 yearsok, Now I see it. The algorithm states that "This algorithm decides which element of a sequence is in the majority". Overlooked the majority part at first look, and assumed its talking about the element appearing maximum number of times. The majority here means that the element should appear at least half the "number of elements" times !
-
Hiroki Osame over 10 yearsYou mean "more than half", instead of "at least half".
-
Anupam Saini over 9 yearsThe explanation from author himself: cs.utexas.edu/users/moore/best-ideas/mjrty/index.html
-
lineil over 8 yearsStep 1 doesn't give you Most Frequent candidate. AAABBCC will give you C as final candidate, but nor is C the most frequent or the majority. Then you run 2nd pass to see this array has no majority.