Python solution using Monte Carlo & Accepted


  • 0
    A

    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
    

  • 1

    Seems like a bad idea to me to reduce it to a set. That reduces the probability of picking the majority element from over 50% to the same probability as every other element.


  • 0
    A

    @StefanPochmann Thanks for correction, I didn't think of that.


  • 0
    Q

    I noticed that U used
    if nums.count(x) > int(len(nums)/2): return x
    I do not understand why u guess, just traverse ll and get the answer.


  • 0
    A

    @quheng Well I didn't put much effort on optimizing my code, just wanted to try this algorithm out. After all it isn't the best algorithm for this problem.


Log in to reply
 

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