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
```