So Monte Carlo here basically works as follows: you randomly guess a number in the list and check if it does appears more than ⌊ n/2 ⌋ times. You set an epsilon which means you have a probability of epsilon to make a wrong answer.

```
import math
import random
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
epsilon = 0.000000000000000000000001
k = int(math.ceil(math.log(1.0/epsilon) / math.log(2.0)))# How many times you want to guess
ll = list(set(nums))
for i in range(1,k+1):
j = random.randint(0, len(ll)-1)
x = ll[j]
if x == 0:
for k in range(0, len(ll)):
j = (j+1) % len(ll)
if ll[j] != 0: break
x = ll[j] * 1
ll[j] = 0
if nums.count(x) > int(len(nums)/2): return x
return 0
```

-Update-

A better version, Thanks to @StefanPochmann. I even once ACed with epsilon=0.1!

```
import math
import random
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
epsilon = 0.01
k = int(math.ceil(math.log(1.0/epsilon) / math.log(2.0)))
for i in range(1,k+1):
j = random.randint(0, len(nums)-1)
x = nums[j]
if nums.count(x) > int(len(nums)/2): return x
return 0
```