python Get K random items based on reservoir sampling


  • 0

    The proof can be proved by induction.
    When I first submit my solution, it won't accept for the long test cases, but when I tried it again, it accepted.
    Ref: reservoir sampling

    class Solution(object):
        def __init__(self, head):
            self.head=head
    
        def getKitem(self,k):
            cur=self.head
            i,res=0,[0]*k
            while cur and i<k:
                res[i]=cur.val
                cur=cur.next
                i+=1
            
            while cur:
                # select j from 0-i
                j=random.randint(0, i)
                # if the pick index less than k, replace it
                if j<k:
                    res[j]=cur.val
                cur=cur.next
                i+=1
            return res
    
        def getRandom(self):
            return self.getKitem(1)[0]
    

Log in to reply
 

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