Time Voting Algorithm. I do not understand

Question

Since I read this ( Find the most common entry in the array ), the Boyer and Moore voice algorithm algorithm was proposed.

If you follow the link to the site, there is a step-by-step explanation of how the algorithm works. For this sequence, AAACCBBCCCBCC it represents the correct solution.

When we move the pointer forward element e:

• If the counter is 0, we set the current candidate to e, and we set against 1.
• If the counter is not 0, we increase or decrease the counter depending on whether e is the current candidate.

When we are done, the current candidate is an element of the majority, if there is a majority.

If I use this algorithm on a piece of paper with AAACCBB as input , the proposed candidate will become B , which is clearly incorrect.

As I see, there are two possibilities

• The authors have never tried their algorithm with anything other than AAACCBBCCCBCC , they are completely incompetent and must be fired on the spot (doubtful).
• I am clearly missing something , should be banned from Stackoverflow, and should never again be allowed to touch anything related to logic.

Note. The following is an implementation of the C ++ algorithm from Niek Sanders. I believe that he correctly implemented this idea and, as such, has the same problem (or isn’t it?).

Answer 1

The algorithm only works when the set has the majority - more than half of the elements are the same. AAACCBB in your example does not have such a majority. The most frequent letter occurs 3 times, the string length is 7.

Answer 2

A small but important addition to other explanations. Moore's voting algorithm has 2 parts -

• The first part of launching the Moore Voting algorithm only gives the candidate for the majority element. Pay attention to the word "candidate".

• In the second part, we need to iterate over the array again to determine if this candidate has a maximum number of times (i.e. more than size / 2 times).

The first iteration is to find the candidate, and the second iteration is to check whether this element is executed most often in the given array.

So, the complexity of time: O(n) + O(n) ≈ O(n)

Answer 3

From the first related 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 the sequence is in the majority, provided that such an element exists

Both of these algorithms explicitly assume that one element has at least N / 2 times . (Note, in particular, that the “majority” does not match the “most common”.)

Answer 4

I wrote C ++ code for this algorithm

 char find_more_than_half_shown_number(char* arr, int len){ int i=0; std::vector<int> vec; while(i<len){ if(vec.empty()){ vec.push_back(arr[i]); vec.push_back(1); }else if(vec[0]==arr[i]){ vec[1]++; }else if(vec[0]!=arr[i]&&vec[1]!=0){ vec[1]--; }else{ vec[0]=arr[i]; } i++; } int tmp_count=0; for(int i=0;i<len;i++){ if(arr[i]==vec[0]) tmp_count++; } if(tmp_count>=(len+1)/2) return vec[0]; else return -1; } 

and the main function is as follows:

 int main(int argc, const char * argv[]) { char arr[]={'A','A','A','C','C','B','B','C','C','C','B','C','C'}; int len=sizeof(arr)/sizeof(char); char rest_num=find_more_than_half_shown_number(arr,len); std::cout << "rest_num="<<rest_num<<std::endl; return 0; } 

Answer 5

When the test case is "AAACCBB", the set does not have the majority. Since no element is found more than three times, since the length of "AAACCBB" is 7.

Here is the code for the “Boyer and Moore Voice Algorithm”:

 int Voting(vector<int> &num) { int count = 0; int candidate; for(int i = 0; i < num.size(); ++i) { if(count == 0) { candidate = num[i]; count = 1; } else count = (candidate == num[i]) ? ++count : --count; } return candidate; }