My understanding of Boyer-Moore Majority Vote

  • 9

    This problem is an extension to 169. Majority Element, which needs Boyer-Moore Majority Vote Algorithm to find the element, whose count is over n/2.

    When I was learning about Boyer-Moore, I was always thinking about the pair. I drew a picture to get myself understandable.

    Suppose there are nine elements in array A, and the round one is the majority.


    No matter in what order we select element from the array, we can only get two results


    Compared to fully pairing, it is a little wasting of the partially pairing as there are some round ones are not paired (definitely it would be left). So, under the condition that the majority element exists, we could only think about the fully pairing situation. (It's useful when dealing with n/3 situation)

    We can consider either column as the candidate, and it's intuitive for me to get understand that the code means found a pair.

    if candidate != element
      count -= 1


    So here comes the n/3 problem, we would only think about the fully pairing situation. If the over one third majority exists, it should be left after pairing.

    Why would we use three elements as a pair? Because it makes sure that in fully pairing the count of majority element equals n/3.

    That's my understanding about Boyer-Moore. Maybe it's not so clear, but it helps me think about it.


    # Modified Boyer-Moore Majority Voting Algorithm
    def majority_element(nums)
      candidate1, candidate2 = 0, 0
      count1, count2 = 0, 0
      # first round to find candidates
      nums.each do |num|
        if candidate1 == num
          count1 += 1
        elsif candidate2 == num
          count2 += 1
        elsif count1 == 0
          candidate1 = num
          count1 += 1
        elsif count2 == 0
          candidate2 = num
          count2 += 1
          # This condition is important, which means a pair out,
          # filtering a set of three elements out
          count1 -= 1
          count2 -= 1
      # second round to confirm
      result = []
      [candidate1, candidate2].uniq.each do |candidate|
        result << candidate if nums.count(candidate) > (nums.count/3)


Log in to reply

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