Python solutions


  • 0
    B

    The space complexity is O(1).

    class Solution(object):
    
        def __init__(self, nums):
            """
            
            :type nums: List[int]
            :type numsSize: int
            """
            self.nums = nums
            
    
        def pick(self, target):
            """
            :type target: int
            :rtype: int
            """
            import random
            m = 0
            temp = 0
            for idx, num in enumerate(self.nums):
                if num == target:
                    t = random.random()
                    if t > m:
                        temp = idx
                        m = t
            return temp       
    

  • 0
    Z

    @buaahsh said in Python solutions:

    m

    Are you sure each index shared same probability in this way?


  • 0

    @zephyr_sails

    It seems that equal probability holds. I did some tedious math on n=3 case:
    [p1,p2,p3]
    suppose p1,p2,p3 are the three independent uniform(0,1) random variable (rv) generated for each of the three positions. It is easy to show that the probability for position 1 being kept is:
    p1^2
    because p1 is rv, to get the actual probability you do the integral:
    integral(from 0 to 1) p1^2 dp1
    and it gives you 1/3!

    To calculate the probability for position 2 being kept is trickier, it is:
    integral(from 0 to 1) [integral(from p1 to 1) p2 dp2] dp1
    this again equals 1/3 (you do the math).

    It makes me feel that there should be some way to actually prove the equal probability by induction. I would love to see some reference on this!


  • 1
    Z

    @bayesric said in Python solutions:

    @zephyr_sails

    It seems that equal probability holds. I did some tedious math on n=3 case:
    [p1,p2,p3]
    suppose p1,p2,p3 are the three independent uniform(0,1) random variable (rv) generated for each of the three positions. It is easy to show that the probability for position 1 being kept is:
    p1^2
    because p1 is rv, to get the actual probability you do the integral:
    integral(from 0 to 1) p1^2 dp1
    and it gives you 1/3!

    To calculate the probability for position 2 being kept is trickier, it is:
    integral(from 0 to 1) [integral(from p1 to 1) p2 dp2] dp1
    this again equals 1/3 (you do the math).

    It makes me feel that there should be some way to actually prove the equal probability by induction. I would love to see some reference on this!

    Thanks, if you think it that way, this algorithm is actually picking up the valid index with biggest rand. So their chance should be the same.


  • 0

    @zephyr_sails

    That is a smart interpretation! Thanks


Log in to reply
 

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