This problem is an extension to 169. Majority Element, which needs Boyer-Moore Majority Vote Algorithm to find the element, whose count is over
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
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 end
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
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 else # This condition is important, which means a pair out, # filtering a set of three elements out count1 -= 1 count2 -= 1 end end # second round to confirm result =  [candidate1, candidate2].uniq.each do |candidate| result << candidate if nums.count(candidate) > (nums.count/3) end result end