The code is based on the elegant Majority Voting algorithm by Moore. (http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html)

Runtime : O(N), Space: O(1)

```
class Solution:
# @param num, a list of integers
# @return an integer
def majorityElement(self, num):
candidate = None
count = 0
for n in num:
if candidate == None:
candidate = n
count += 1
elif n == candidate:
count += 1
elif n != candidate and count == 1:
candidate = None
count -= 1
elif n != candidate:
count -= 1
return candidate
```