Boyer-Moore Majority Vote algorithm generalization


  • 63
    M

    Boyer-Moore Majority Vote algorithm generalization to elements appear more than floor(n/k) times

    class Solution {
    public:
      vector<int> majorityElement(vector<int> &a) {
        int y = 0, z = 1, cy = 0, cz = 0;
        for (auto x: a) {
          if (x == y) cy++;
          else if (x == z) cz++;
          else if (! cy) y = x, cy = 1;
          else if (! cz) z = x, cz = 1;
          else cy--, cz--;
        }
        cy = cz = 0;
        for (auto x: a)
          if (x == y) cy++;
          else if (x == z) cz++;
        vector<int> r;
        if (cy > a.size()/3) r.push_back(y);
        if (cz > a.size()/3) r.push_back(z);
        return r;
      }
    };

  • 0

    Hi, MaskRay. Thank you for your sharing. Could you give some explanations for the above code or provide some links w.r.t the algorithm? Thanks!


  • 0
    J

    At most have two numbers appear more than 1/3,If a number's frequent >1/3,then it must have recorded as y or z,because other number's frequent <1/3,they cann't minus y or z out.


  • 0

    Hi, johnlao. Thank you. I have got the idea.


  • 14
    D

    for java form

    public class Solution {
    public List<Integer> majorityElement(int[] nums) {
     //there should be at most 2 different elements in nums more than n/3
     //so we can find at most 2 elements based on Boyer-Moore Majority Vote algo
     List<Integer> res = new ArrayList<Integer>();
     if(nums.length==0) return res;
     int count1=0,count2=0,m1=0,m2=0;
     for(int n : nums){
         if(m1==n) count1++;
         else if(m2==n) count2++;
         else if(count1==0) {
             m1=n;
             count1=1;
         }
         else if(count2==0) {
             m2=n;
             count2=1;
         }
         else{
             count1--;
             count2--;
         }
     }
     count1=0;
     count2=0;
     //count the number for the 2 elements
     for(int n:nums){
         if(n==m1) count1++;
         else if(n==m2) count2++;
     }
     //if those appear more than n/3
     if(count1>nums.length/3) res.add(m1);
     if(count2>nums.length/3) res.add(m2);
     return res;
    
       }
    }
    

  • 0
    Z

    Just curious, if we initialize y and z to the same value (e.g., 0), the above solution should still work, right?


  • 0

    Hi, zhukov. I try it and it works.


  • 0
    Z

    Thank jinchao for the confirmation. I have tried it and it worked, too. I think that if we initialize y and z to the same value (e.g., 0), the only special case is that the numbers are all 0 and it can still be properly handled by the second loop. Other cases are essentially handled in the same way as y and z are initialized to different values.


  • 0

    Hi, zhukov. Thank you for your nice observations. Well, I have not thinked that deep as you do :-)


  • 0
    C
    This post is deleted!

  • 0
    M

    I have tested [51, 24, 24, 43, 24, 38, 32, 9] and the solution passed.


  • 0
    C

    Weird....it works this time...maybe I was wrong, sorry about that


  • 0
    S

    Hi all, the initial value of y=0 and z=1 seems not-so-easy-to-understand for me. So i changed the first for loop a little:

    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            vector<int> majorities;
            int a, b, numa = 0, numb = 0;
            for(auto x: nums) {
                if (numa == 0) {
                    a = x;
                    numa = 1;
                } else if (x == a) {
                    numa++;
                } else if (numb == 0) {
                    b = x;
                    numb = 1;
                } else if (x == b) {
                    numb++;
                } else {
                    numa--;
                    numb--;
                }
            }
            numa = numb = 0;
            for(auto x: nums) {
                if (x == a) {
                    numa++;
                } else if (x == b) {
                    numb++;
                }
            }
            if (numa > nums.size()/3) {
                majorities.push_back(a);
            }
            if (numb > nums.size()/3) {
                majorities.push_back(b);
            }
            return majorities;
        }
    }; 
    

  • 0
    K

    Hi MaskRay, I don't think your generalized algorithm works for any value "k" such that elements appear more than floor(n/k) times. You are assuming that the number of majority elements that can exists is atmost two for any value of "k" which is incorrect.
    For example: if k = 4 and n=16 then there can be 3 majority elements each appearing 5 times correct?


  • 0
    A

    Hi,jianchao.li.fighter.I test your code, it will be wrong for this case:[1,2,2,3,2,1,1,3].I wonder if there is something wrong.


  • 0

    Where did I post any code? The code is not mine...


  • 0
    A

    oh,sorry : )


  • 0
    L

    @MaskRay

    Have been confused why if (x==y) else if (x==z) is done first and then if (!cy) .. if (!cz)... part? why not;

    if (! cy) y = x, cy = 1;
    else if (! cz) z = x, cz = 1;
    else if (x == y) cy++;
    else if (x == z) cz++;
    

    Can anyone elaborate?


  • 0
    W

    @leaper We should make sure y and z point to different numbers, if let if (!cy) .. if (!cz)... first at first y and z are both a[0], you can check this test case [8,8,7,7,7] for example.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.