Ruby Solution - Boyer-Moore Majority Vote Algorithm


  • 0
    I

    Refer to Boyer-Moore Majority Vote Algorithm, it has O(N) time and O(1) space. Marvelous!

    There is a wonderful article talking about the algorithm: Majority Voting Algorithm - Blog of Greg Grothaus

      # Using Boyer-Moore Majority Voting Algorithm
      def majority_element(nums)
        candidate = nil
        count = 0
    
        # first round to find candidate
        nums.each do |ele|
          candidate = ele if count == 0
    
          if candidate == ele
            count += 1
          else
            count -= 1
          end
        end
    
        # second round to confirm
        count = 0
        nums.each do |ele|
          count += 1 if ele == candidate
        end
    
        count > nums.count/2 ? candidate : nil
      end
    

Log in to reply
 

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